单源最短路(SSSP)的算法有Dijkstra，Bellman-Ford，两大算法优化后即为Dijkstra+heap与SPFA。

这两个优化版算法写起来非常相似。接下来就从算法思路、时间复杂度、写法和适用场景上进行对比分析。

基础算法

Dijkstra

时间复杂度：O(V2+E)

n-1次循环

–>找到未标记的d最小的点

–>标记，松弛它的边

void dijkstra(int s){
    memset(vis, false, sizeof(vis));
    vis[s] = true;
    for(int i = 1; i <= n; i++)
        dis[i] = road[s][i];
    for(int u = 1; u<n; u++){
        int minD = inf,k = -1;
        for(int i = 1; i<= n; i++){
            if(!vis[i]&&dis[i]<minD){
                k = i;
                minD = dis[i];
            }
        }
        vis[k] = true;
        for(int i = 1; i<= n; i++){
            if(!vis[i]&&dis[k]+road[k][i]<dis[i]){
                dis[i]=dis[k]+road[k][i];
            }
        }
    }
}

Bellman-Ford

时间复杂度：O(VE)

n-1次循环

–>对所有边松弛

还能再松弛则有负环

int dis[10010];
int u[10010],v[10010],w[10010];
int n,m;
void Bellman_ford(int a){
    memset(dis,inf,sizeof(dis));//赋初始值
    dis[a]=0;
    for(int i=1;i<=n-1;i++)//更新n-1次
        for(int j=1;j<=m;j++)//更新每一条边
            dis[v[j]]=min(dis[v[j]],dis[u[j]]+w[j]);//判断是否更新
 }

两大基础算法对比

Dijkstra是每次确定了到一个点的最短距离，再用该点更新到其它点的距离。不能处理有负边的图。
Bellman-Ford是每次对所有边松弛。可以计算出有负边无负环的最短路，可以判断是否存在负环。

优化算法

Dijkstra+heap优化

时间复杂度：O((V+E)lgV)

用STL中的优先队列实现堆：

while(优先队列非空)

–>队头出队，松弛它的边

–>松弛了的<新距离,点>入队

typedef pair<int,int> PII;
priority_queue<PII,vector<PII>,greater<PII> > q;
...
while(!q.empty()){  // O(V) 加上count<n可以优化一点点 
    int w=q.top().first, u=q.top().second;
    q.pop();   // O(lgV)
    if(b[u])continue; b[u]=true;
    //++count;
    for(int i=head[u];i;i=e[i].next){ // Sum -> O(E)
        int v=e[i].to;
        if(d[u]+e[i].w<d[v]){
            d[v]=d[u]+e[i].w;
            q.push(PII(d[v],v));  // O(lgV)
        }
    }
}

SPFA

时间复杂度：O(kE) or O(VE)

while(队非空)

–>队头出队，松弛它的边

–>松弛了且不在队内的点入队

while(!q.empty()){
    int u=q.front(); q.pop();
    b[u]=false;
    for(int i=head[u];i;i=e[i].next){
        int v=e[i].to;
        if(d[u]+e[i].w<d[v]){
            d[v]=d[u]+e[i].w;
            if(!b[v])b[v]=true,q.push(v);
        }
    }
}

算法思路对比

Dijkstra+heap是用小根堆，每次取出d最小的点，来更新距离，那么这个点来说，最小距离就是当前的d。
SPFA是用双端队列，每次取出队头，来更新距离，它之后可能还会入队。它是一种动态逼近法，因为每次松弛距离都会减小，所以松弛一定会有结束的。如果一个点入队超过n次就是存在负环。

复杂度分析对比

Dijkstra+heap

因为是堆，取队头需要O(lgV)。
松弛边时，因为点的d改变了，所以点v需要以新距离重新入堆，O(lgV)，总共O(ElgV)。
因此总的是O((V+E)lgV)

SPFA

论文证明也不严格。复杂度不太好分析。
~~总的是O(kE)。k大概为2~~。
复杂度应该是 O(VE)。

适用场景

如果是稠密图，Dijkstra+heap比SPFA快。稀疏图则SPFA更快。SPFA可以有SLF和LLL两种优化，SLF就是d比队头小就插入队头，否则插入队尾。

另外，Dijkstra和Prim也很相似，它们的区别主要是d的含义，前者是到s的临时最短距离，后者是到树的临时最短距离，相同点是，每次找d最小的更新其它点的距离。

Dijkstra堆优化版代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll maxx = 0x3f3f3f3f3f3f3f3f;
const int maxn = 1e5+7;
int t,n,m,cnt;
ll dis[maxn];
bool vis[maxn];
int head[maxn];
struct EDGE{
    int next;
    int to;
    ll w;
}edge[2*maxn];
struct NODE{
    int u;
    ll dis;
    NODE(){}
	NODE(int u,ll w):u(u),dis(w){}
	bool operator <(const NODE &a)const
	{
		return dis>a.dis;
	}
}node[2*maxn];
void add(int u, int v, ll w){
    edge[cnt].next = head[u];
    edge[cnt].to = v;
    edge[cnt].w = w;
    head[u] = cnt;
    cnt++;
}
void dijkstra(int s){
    memset(dis,maxx,sizeof(dis));
    memset(vis,false,sizeof(vis));
    priority_queue<NODE>q;
    q.push(NODE(s,0));
    while(!q.empty()){
        int kk = q.top().u;
        ll minD = q.top().dis;
        q.pop();
        if(vis[kk])
            continue;
        vis[kk] = true;
        for(int l = head[kk]; l!=-1; l=edge[l].next){
            if(!vis[edge[l].to]&&minD + edge[l].w < dis[edge[l].to]){
                dis[edge[l].to] = minD + edge[l].w;
                q.push(NODE(edge[l].to,dis[edge[l].to][j]));
            }
        }
    }
}
int main(){
    ll u,v,w;
    scanf("%d",&t);
    while(t--){
        memset(head,-1,sizeof(head));
        cnt = 0;
        scanf("%d%d",&n,&m);
        for(int i = 0;i < m; i++){
            scanf("%d%d%lld",&u,&v,&w);
            add(u,v,w);
        }
        dijkstra(1);
        if(dis[n]!=maxx)
        	printf("%lld\n",dis[n]);
        else
            printf("0\n");
    }
    return 0;
}