单源最短路

发表于

Hello!

单元最短路算法是图论中比较重要的算法，往往配合其他算法发挥重要作用。然而，各种讲解比较混乱，没有一个通用的模板来理解和记忆。

N、M、S，分别表示点的个数、有向边的个数、出发点的编号

SPFA

主要思想：初始时将起点加入队列。每次从队列中取出一个元素，并对它所相邻的点进行修改，若某个相邻的点修改成功，则将其入队。直到队列为空算法结束。（和广搜类似。。。）适用于稀疏图和负权

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

inline void spfa(){
    queue<int> q;   
    for(int i=1; i<=n; i++) dis[i]=2147483647;//赋初值  
    int u,v; q.push(s);//stl模板库里的一些函数大佬们应该都明白吧。。。  
    dis[s]=0; vis[s]=1;   
    while(!q.empty()){//队列优化 
        u=q.front();  
        q.pop(); vis[u]=0; 
        for(int i=head[u];i;i=h[i].next){//SPFA最重要的遍历图 
            v=h[i].to;  
            if(dis[v]>dis[u]+h[i].w){   
                dis[v]=dis[u]+h[i].w; 
                if(!vis[v]){ 
                    vis[v]=1;
                    q.push(v);
                }
            }
        }
    }
}

Dijkstra

主要思想：一开始将起点到起点距离设为0，而后进行n次循环，每次找出一个到起点距离最短的点u，进行标记。随后枚举所有没有被标记的点，如果以此标记的点中转到达没有标记的点v的路径更短，将此更短路径作为dis[v]，无法处理负权图，适用于稠密图。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

inline void dijkstra(){
    for(int i=1;i<=n;i++) dis[i]=2147483647;  
    dis[s]=0; 
    for(int i=1;i<=n;i++){ 
        mi=214748364,t=-1; 
        for(int j=1;j<=n;j++){ 
            if(!vis[j] && dis[j]<mi){ 
                mi=dis[j]; t=j; 
            } 
        } 
        if(t==-1) break; 
        vis[t]=1; 
        for(int j=head[t];j;j=h[j].next){//前向星遍历图大法
            if(!vis[h[j].to]&&dis[h[j].to]>(h[j].w+dis[t]))
            dis[h[j].to]=h[j].w+dis[t];
        }
    }
}

Floyd

最简单的最短路，类似动归，可以处理正负边权

方法：1，从任意一条单边路径开始。所有两点之间的距离是边的权，如果两点之间没有边相连，则权为无穷大。

2，对于每一对顶点 u 和 v，看看是否存在一个顶点 w 使得从 u 到 w 再到 v 比已知的路径更短。如果是更新它。

但是，无论时间(O(n^3))还是空间，效率都太低:( 可以备用～～～

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

#include<bits/stdc++.h>
using namespace std;
inline int read(){    //快读
int x=0,k=1; char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')k=-1;c=getchar();}
    while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+(c^48),c=getchar();
    return x*k;
}
int a[2000][2000],n,m,s;//用邻接矩阵来存图即可...
inline void floyd(){//floyd模板就不解释了
    for(int k=1;k<=n;k++)
        for(int i=1;i<=n;i++){
            if(i==k||a[i][k]==100000000)//一点小优化
                continue; 
            for(int j=1;j<=n;j++){
                if(i==j||j==k||a[k][j]==100000000)
                    continue;
                a[i][j]=min(a[i][j],a[i][k]+a[k][j]);
            }
        }
    }
}
int main(){
    n=read(),m=read(),s=read();
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)a[i][j]=100000000;
    for(int i=1,u,v,w;i<=m;i++){
        u=read(),v=read(),w=read();
        a[u][v]=min(a[u][v],w);//
    }
    floyd();
    for(int i=1;i<=n;i++)
        if(i==s)
            printf("0 ");
        else if(a[s][i]==100000000)
            printf("2147483647 ");
        else
            printf("%d ",a[s][i]);
    return 0;
}

Floyd也可以判断一图中两点是否连通

1
2
3
4
5
6

//初始设置：相连的两点 dis[i][j]=true;反之亦然
for(k=1;k<=n;++k)
    for(i=1;i<=n;++i)
        for(j=1;j<=n;++j)
        dis[i][j]=dis[i][j]||(dis[i][k]&&dis[k][j]);

See Also

以上三种算法仅仅是常用的三种简单算法，要根据情况进行选择。

附SPFA和Dijkstra的函数部分

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

#include<bits/stdc++.h>
using namespace std;
inline int read(){
    int x=0,k=1; char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')k=-1;c=getchar();}
    while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+(c^48),c=getchar();
    return x*k;
}
int n,m,s,tot=0,dis[10005],head[500005],mi,t;
bool vis[10005];
struct Edge{
     int next,to,w;
}h[500005];//结构体存边
void add(int u,int v,int w){
    h[++tot].next=head[u];
    h[tot].to=v;
    h[tot].w=w;
    head[u]=tot;
}//前向星存边
int main(){
    n=read(),m=read(),s=read();
    for(int i=1,u,v,w;i<=m;i++){
        u=read(),v=read(),w=read(); 
        add(u,v,w);
    }
    spfa();
    for(int i=1; i<=n; i++)
        printf("%d ",dis[i]);
    return 0;
}