最短路

单源最短路：dijkstra

dijkstra用于解决单源最短路问题，即起点唯一，终点不唯一
适用于稠密图，算法时间复杂度\(O(n^2)\)
该算法要求图中不能有负环
通过从起始点向外扩散，不断进行松弛操作，dis[i]表示从起点到当前点的最短的路径长度

dijkstra的贪心策略用在最长路上是错误的！！！

朴素写法

其实，邻接矩阵存图效率过低 只是来枚举行和列来找到距离最近的

#include<bits/stdc++.h>
using namespace std;
#define clean(a, b) memset(a, b, sizeof(a))
const int inf=0x3f3f3f3f;
const int maxn=1e4+9;
int n,m,s,t;
int mp[maxn][maxn],dis[maxn],vis[maxn];
void dijkstra(int now)
{
    clean(vis,0);//标记是否被处理过
    for(int i=1;i<=n;i++)
    {
        dis[i]=mp[now][i];//初始距离
    }
    dis[now]=0;//当前点到他自己的最短距离是0
    vis[now]=1;//当前点被处理过了
    int temp,j,k;
    for(int i=1;i<=n;i++)
    {
        temp=inf;
        for(j=1;j<=n;j++)
        {
            if(!vis[j]&&temp>dis[j])//找有没有没被处理
            {
                k=j;
                temp=dis[j];
            }
        }//找一个要拿来松弛的中间点
        if(temp==inf) break;
        vis[k]=1;
        for(j=1;j<=n;j++)//对每一个点进行松弛操作
        {
            if(!vis[j]&&dis[j]>dis[k]+mp[k][j]);
            {
                dis[j]=dis[k]+mp[k][j];
            }
        } 
    }
}
int main()
{
    scanf("%d%d",&n,&m);
    int u,v,w;
    for(int i=1;i<=n;i++)//预处理把边权记成inf
    {
        for(int j=1;j<=n;j++)
        {
            mp[i][j]=inf;
        }
    }
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d%d",&u,&v,&w);
        if(mp[u][v]>w) mp[u][v]=mp[v][u]=w;//无向图
    }
    scanf("%d%d",&s,&t);
    dijkstra(s);//从s开始搜
    if(dis[t]==inf) puts("-1");//没有路
    else printf("%d\n",dis[t]);//最短路
    return 0;
}

堆优化

堆优化的主要思想就是使用一个优先队列（就是每次弹出的元素一定是整个队列中最小的元素）来代替最近距离的查找，用邻接表代替邻接矩阵，这样可以大幅度节约时间开销
我们将结点的编号，到起点的距离存到一个struct中，然后每次将他推入优先队列，这样每次弹出的所代表的距离一定是最短的，如果一个结点到起点的距离发生了变化，那就一定是变得更短了，所以我们每次只取队首就是最优的，顺便标记一下，如果用过了就continue

复杂度\(O(2*E+V*logV)\)

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define lowbit(a) ((a) & -(a))
#define clean(a, b) memset(a, b, sizeof(a))
const int mod = 1e9 + 7;
const int inf = 0x3f3f3f3f;
const int maxn = 5e5 + 9;

int _;

//========================================================================
struct edge
{
    int to,cost,next;
}e[maxn];
int top,head[maxn],vis[maxn],dis[maxn];
void init()
{
    top=0;
    memset(head,-1,sizeof(head));
}
void insert_(int u,int v,int c)
{
    e[top].to=v;
    e[top].cost=c;
    e[top].next=head[u];
    head[u]=top++;
}
struct node
{
    int num,dist;
    bool operator < (const node &x) const
    {
        return dist>x.dist;
    }
};
priority_queue<node>q;
//========================================================================
int main()
{
    init();
    int n,m,s,u,v,w;
    scanf("%d%d%d",&n,&m,&s);
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d%d",&u,&v,&w);
        insert_(u,v,w);
    }
    for(int i=1;i<=n;i++) dis[i]=2147483647; 
    dis[s]=0;
    q.push(node{s,0});
    while(!q.empty())
    {
        node x=q.top();
        q.pop();
        int y=x.num;
        if(vis[y]) continue;
        vis[y]=1;
        for(int i=head[y];i!=-1;i=e[i].next)
        {
            if(dis[e[i].to]>dis[y]+e[i].cost)  
            {
                dis[e[i].to]=dis[y]+e[i].cost;
                q.push(node{e[i].to,dis[e[i].to]});
            }
        }
    }
    for(int i=1;i<=n;i++) 
    {
        printf("%d ",dis[i]);
    }
    printf("\n");
    return 0;
}

话说，dijkstra+配对堆 应该不常用得到吧……

spfa

[最短路回顾]

原文：https://www.cnblogs.com/YangKun-/p/13322289.html