超详细！图论最短路算法与极简c++代码（配题目）_给定一个 n 个点 m 条边的有向图,图中可能存在重边和自环,所有边权均为非负值。

最短路算法知识结构图

/*
最短路问题{
    单源最短路{
        1.所有边权都是正数{
            1.朴素Dijkstra算法 O(n^2) 适用于稠密图
            
            2.堆优化的Dijkstra O(mlog(n)) 适用于稀疏图
        }
        
        2.存在负权边{
            1.Bellman-Ford O(nm)
            
            2.SPFA 一般O(m)最坏O(nm)
        }
    }
    多源汇最短路{
			Floyed算法	        
    }
}
*/
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

稠密图：一般边数m=n^2

稀疏图：边数m=n

Dijkstra基于贪心算法

Floyed基于动态规划

Bellman-Ford基于离散数学中的知识

---

朴素版Dijkstra算法

s={当前已经确定最短距离的点}

1.初始化

dis[1]=0,dis[otherwise]=+∞
1

2.循环迭代(贪婪规则：更新当前还没有确定的点中距离最小的点）

for(i:0~n)迭代循环n次
不在s中的距离最近的点->t
t->s //将t加到s集合内
用t来更新其他点的距离(check(dis[x]>dis[t])
1
2
3
4

3.可确定每一个点到起点的最短距离了

存法：使用邻接矩阵(因为是稠密图)

下面是一道例题：

例题：

给定一个 n 个点 m 条边的有向图，图中可能存在重边和自环，所有边权均为正值。

请你求出 1 号点到 n 号点的最短距离，如果无法从 1 号点走到 n 号点，则输出 −1。

输入格式

第一行包含整数 n 和 m。

接下来 m 行每行包含三个整数 x,y,z，表示存在一条从点 x 到点 y 的有向边，边长为 z。

输出格式

输出一个整数，表示 1 号点到 n 号点的最短距离。

如果路径不存在，则输出 −1。

数据范围

1≤n≤500,
1≤m≤105,

ps.图中涉及边长均不超过10000。

输入样例：

3 3

1 2 2

2 3 1

1 3 4

输出样例：

3

朴素Dijstra解法：

#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define MAXN 510

int n,m;
int dis[MAXN],g[MAXN][MAXN];
bool st[MAXN];

int dijkstra(){
    memset(dis,0x3f3f3f3f,sizeof(dis));
    dis[1]=0;
    for(int i=0;i<n;i++){
        int t=-1;
        
        for(int j=1;j<=n;j++)
            if(!st[j] && (t==-1||dis[t]>dis[j]))
                t=j;
		if(t==n) break;
        st[t]=true;
        
        for(int j=1;j<=n;j++)
            dis[j]=min(dis[j],dis[t]+g[t][j]);
    }
    //判断一下是否是孤立点
    if(dis[n]==0x3f3f3f3f) return -1;
    return dis[n];
}

int main(){
    memset(g,0x3f,sizeof(g));
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++){
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        g[a][b]=min(g[a][b],c);
    }
    int t=dijkstra();
    printf("%d\n",t);
    
    return 0;
}
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
42
43

---

如果是稀疏图的话，对照上面的朴素Dijkstra，我们可以在这一步：

2.循环迭代(贪婪规则：更新当前还没有确定的点中距离最小的点）

for(i:0~n)迭代循环n次
不在s中的距离最近的点->t  ****************O(n^2)
t->s //将t加到s集合内
用t来更新其他点的距离(check(dis[x]>dis[t]) ***O(mlogn)
1
2
3
4

***********处使用堆来进行优化，直接借助于STL中的prority_queue或者手写堆（Python中的set）

bfs的迭代方式

1.先将(0,1)放入优先队列 //必须是小根堆
2.while！empty:取堆顶元素并弹出,如果此点已经被更新过了则继续迭代。
否则用当前点来更新其他点(遍历邻接表)，记住，一定要将此点放入st[]数组来被标记
如果当前点距离大于从最近元素过来的距离，则更新dis[]并把j点放入优先队列；
3.最后结束的时候需要判断是否是孤立点，即是否为连通图
1
2
3
4
5

---

### 例题：

给定一个 n 个点 m 条边的有向图，图中可能存在重边和自环，所有边权均为非负值。

请你求出 1 号点到 n 号点的最短距离，如果无法从 1 号点走到 n 号点，则输出 −1。

输入格式

第一行包含整数 n 和 m。

接下来 m 行每行包含三个整数 x,y,z，表示存在一条从点 x 到点 y 的有向边，边长为 z。

输出格式

输出一个整数，表示 1 号点到 n 号点的最短距离。

如果路径不存在，则输出 −1。

数据范围

1≤n,m≤1.5×105,
图中涉及边长均不小于 0，且不超过 10000。

输入样例：

3 3
1 2 2
2 3 1
1 3 4

输出样例：

3

AC代码：

#include<bits/stdc++.h>
#include<iostream>
#include<string>
#include<algorithm>
#include<string.h>
#include<queue>
#define MAXN 160010
using namespace std;

typedef pair<int,int> pii;

//使用邻接表存储稀疏图
int n,m,idx;
int h[MAXN],e[MAXN],ne[MAXN],w[MAXN];//h[]存储每个邻接表上的头结点；ne[]存的是每个节点的下一个节点，即next；w存储权重
int dis[MAXN];
bool st[MAXN];
//pair的first存的是距离，second存的是编号

void add(int a,int b,int c){
    e[idx]=b,w[idx]=c;
    ne[idx]=h[a],h[a]=idx++;
}

int dijkstra(){
    memset(dis,0x3f,sizeof(dis));
    dis[1]=0;
    
    priority_queue<pii,vector<pii>,greater<pii>> heap; //存储一个小根堆
    heap.push({0,1});
    
    while(heap.size()){
        auto u = heap.top();heap.pop();
        
        int ver = u.second,distance = u.first;  //ver存储点的序号，distance存储距离
        if(st[ver]) 
            continue;
        st[ver]=true; //这nm千万别忘了啊
        for(int i=h[ver];i!=-1;i=ne[i]){
            int j=e[i];
            if(dis[j]>distance+w[i]){
                dis[j]=distance+w[i];
                heap.push({dis[j],j});
            }
        }
    }
    if(dis[n]==0x3f3f3f3f) return -1;
    return dis[n];
}

int main(){
    scanf("%d%d",&n,&m);
    memset(h,-1,sizeof(h));
    while(m--){
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        add(a,b,c);
    }
    int t=dijkstra();
    printf("%d\n",t);
    return 0;
}
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
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61

---

Bellman_Ford算法 O(n*m)

任意存边方式都可，建议结构体

for(n次){
	备份（防止用更新过的点更新其他点）
	for 所有从a走到b的边，权重是w{
		dis[b]=min(dis[b],dis[a]+w);
	}
}
1
2
3
4
5
6

循环完，所有边都满足三角不等式dis[b]<=dis[a]+w;迭代k次表示经过超过k条边的最短路的距离。如果第n次迭代仍然有边更新，根据抽屉原理，说明有负环。因此，Bellman-Ford算法可以用来找负环。

注意：如果有负权回路，最短路不一定存在

例题：

给定一个 n 个点 m 条边的有向图，图中可能存在重边和自环， 边权可能为负数。

请你求出从 1 号点到 n 号点的最多经过 k 条边的最短距离，如果无法从 1 号点走到 n 号点，输出 impossible。

注意：图中可能 存在负权回路 。

输入格式

第一行包含三个整数 n,m,k。

接下来 m 行，每行包含三个整数 x,y,z，表示存在一条从点 x 到点 y 的有向边，边长为 z。

输出格式

输出一个整数，表示从 1 号点到 n 号点的最多经过 k 条边的最短距离。

如果不存在满足条件的路径，则输出 impossible。

数据范围

1≤n,k≤500,
1≤m≤10000,
任意边长的绝对值不超过 10000。

输入样例：

3 3 1
1 2 1
2 3 1
1 3 3

输出样例：

3

AC代码：

#include<iostream>
#include<algorithm>
#include<string>
#include<cstring>
using namespace std;
#define MAXN 10010
#define maxn 510

struct Edge{
    int a,b,w;  
} edge[MAXN];

int dis[MAXN],backup[MAXN];
int n,m,k;

int bellman_ford(){
    memset(dis,0x3f,sizeof(dis));
    dis[1]=0;
    //n次迭代
    for(int i=1;i<=k;i++){
        memcpy(backup,dis,sizeof(dis));
        for(int j=1;j<=m;j++){
            int a=edge[j].a,b=edge[j].b,w=edge[j].w;
            dis[b]=min(dis[b],backup[a]+w);
        }
    }
    if(dis[n]>0x3f3f3f3f/2) return -1;
    return dis[n];
}

int main(){
    scanf("%d%d%d",&n,&m,&k);
    for(int i=1;i<=m;i++){
        int a,b,w;
        scanf("%d%d%d",&a,&b,&w);
        edge[i].a=a,edge[i].b=b,edge[i].w=w;
    }
    int t=bellman_ford();
    if(t==-1) puts("impossible");
    else printf("%d\n",t);
    return 0;
}
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
42

---

SPFA算法

步骤：

0.用邻接表存储
1.队头入队，更新st数组
2.BFS思路while队列不空,t<-q.front(),p.pop()
3.遍历t的邻接表，更新dis[]数组，即t每一出点的最小距离；
4.在每一出点判断，如果不在队列里，则加入队列；
5.最后迭代完之后的判断
1
2
3
4
5
6

例题：

请你求出 1 号点到 n 号点的最短距离，如果无法从 1 号点走到 n 号点，则输出 impossible。

数据保证不存在负权回路。

输入格式

第一行包含整数 n 和 m。

接下来 m 行每行包含三个整数 x,y,z，表示存在一条从点 x 到点 y 的有向边，边长为 z。

输出格式

输出一个整数，表示 1 号点到 n 号点的最短距离。

如果路径不存在，则输出 impossible。

数据范围

1≤n,m≤105,
图中涉及边长绝对值均不超过 10000。

输入样例：

3 3
1 2 5
2 3 -3
1 3 4

输出样例：

2

AC代码：

#include<iostream>
#include<string>
#include<algorithm>
#include<string.h>
#include<queue>
#define MAXN 160010
using namespace std;

typedef pair<int,int> pii;

//使用邻接表存储稀疏图
int n,m,idx;
int h[MAXN],e[MAXN],ne[MAXN],w[MAXN];//h[]存储每个邻接表上的头结点；ne[]存的是每个节点的下一个节点，即next；w存储权重
int dis[MAXN];
bool st[MAXN];
//pair的first存的是距离，second存的是编号

void add(int a,int b,int c){
    e[idx]=b,w[idx]=c;
    ne[idx]=h[a],h[a]=idx++;
}

int spfa(){
    memset(dis,0x3f,sizeof(dis));
    dis[1]=0;
    
    queue<int> Q;
    Q.push(1);
    st[1]=true;
    while(Q.size()){
        int t=Q.front();Q.pop();
        st[t]=false;
        
        for(int i=h[t];i!=-1;i=ne[i]){
            int j=e[i];
            if(dis[j]>dis[t]+w[i]){
                dis[j]=dis[t]+w[i];
                if(!st[j]){
                    Q.push(j);
                    st[j]=true;
                }
            }
        }
    }
    if(dis[n]==0x3f3f3f3f) return -1;
    return dis[n];
}

int main(){
    scanf("%d%d",&n,&m);
    memset(h,-1,sizeof(h));
    while(m--){
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        add(a,b,c);
    }
    int t=spfa();
    if(t==-1) puts("impossible");
    else printf("%d\n",t);
    return 0;
}
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
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61

Floyed算法 O(n^3)

1.邻接矩阵d[i][j]存图中每个点

for(k=1~n){
	for(i=1~n){
		for(j=1~n){
			d[i][j]=min(d[i][j],d[i][k]+d[k][j];
		}
	}
}
1
2
3
4
5
6
7

d[k,i,j]表示从i点经过1~k中间点到达j的最短距离
因此基于动态规划的状态转移方程为：

d[k,i,j]=min(d[k,i,j],d[k-1,i,k]+d[k-1,k,j])
1

从i到j只经过k-1这些点，再从k到j只经过1_{k-1这些点，加在一起就是从i}j经过k个点,而k-1可以压缩掉，故状态转移方程为

d[i][j]=min(d[i][j],d[i][k]+d[k][j];
1