图论最短路算法

本文主要是介绍图论最短路算法，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

图论最短路讲的并不是两点之间线段最短，对于有向图or无向图来讲，最短路表示的路径上（边上）权值和的大小，如果是最小，我们称这是图的最短路；

最短路算法大致分：多对多，单对多，单对单；

而根据算法的类型不同，图的最短路算法有这三种算法：floyd-warshall,bellman-ford,dijkstra;

对比这三种算法，我们可以可以用这样一个图来概括这三种算法的应用类型和应用范围:

而且，我们可以简单将最短路算法分为两类算法：多源最短路和单源最短路算法，其中，弗洛伊德算法是多源最短路径算法，而另外两种算法则是单源最短路径算法；

我接下来就根据我这几天学习最短路径算法浅浅的谈一下对这三种算法的理解

1.floyd（弗洛伊德算法，多源最短路径算法）

佛洛依德算法被人们亲切的描述成“三循环”算法，这是因为弗洛伊德算法的核心就是在于循环的嵌套，相应的，其算法时间复杂度是O（3*n）；

并且对于佛洛依德来说，是一次性求所有节点的最短路径

可惜的是，佛洛依德算法虽然简单好理解，但是耐不住他用邻接矩阵来存储图，这太有局限性了，所以说这种存储方式只能将佛洛依德算法的应用范围控制在200个点的图以内；

而对于弗洛伊德算法，大致讲了个什么呢？

这个请自行了解，算法核心就是动态规划的思想，然后就完事了，当然，具体内容建议参考相关的数据结构书

这里有一个例题：

https://acm.sdut.edu.cn/onlinejudge3/contests/3988/problems/A

Talk is cheap. Show me the code.

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 int n,m;
 4 int graph[110][110];
 5 const int INF=0x3f3f3f3f;
 6 void floyd()
 7 {
 8     int s=1;//起点 
 9     for(register int k=1;k<=n;k++)//中间点 
10     {
11         for(register int i=1;i<=n;i++)//起点 
12         {
13             if(graph[i][i]<=0)//判负圈 
14             graph[i][i]=0;
15             if(graph[i][k]!=INF)//这个优化对于特定的题目来说是不可或缺的 
16             for(register int j=1;j<=n;j++)//终点 
17             {
18                 if(graph[i][j]>graph[i][k]+graph[k][j])
19                 {
20                     graph[i][j]=graph[i][k]+graph[k][j];
21                 }
22             }
23         }
24     }
25     printf("%d\n",graph[s][n]);//输出 
26 }
27 int main()
28 {
29     while(~scanf("%d %d",&n,&m))
30     {
31         for(register int i=1;i<=n;i++)
32         {
33             for(register int j=1;j<=n;j++)
34             {
35                 if(i==j)//自己到自己的距离是0 
36                 {
37                     graph[i][j]=0;
38                 }
39                 else
40                 {
41                     graph[i][j]=INF;//先设为无穷大 
42                 }
43             }
44         }
45             while(m--)
46             {
47                 int a,b,c;
48                 scanf("%d %d %d",&a,&b,&c);
49                 if(graph[a][b]>c)
50                 {
51                     graph[a][b]=graph[b][a]=c;//邻接矩阵存图，并且是双边情况 
52                 }
53             }
54             floyd();
55         }
56     return 0;
57         
58 } 

2.bellman-ford贝尔曼福特（福德）算法

对于更广范围的图来说，贝尔曼福特是一种优质的选择，并且，贝尔曼福德算法是解决单源最短路径算法的：给定起点s,求到图中所有节点的最短路径

贝尔曼算法的特点是只对节点进行计算，相比floyd，这避免了大撒网式的无效计算；

而关于这个算法的具体思想和实现，依旧是需要自己去努力理解它；

这里只提供bellman在现实中的一个模型-警察问路模型：

Bellman Ford有现实的模型，即问路。每个十字路上站着一个警察;在某个路口，路人问一个警察，怎么走到s最近?如果这个警察不知道，他会相邻几个路口的警察:“从你这个路口走,能到s吗?有多远?”这些警察可能也不知道，他们会继续问新的邻居。这样传递下去，最后肯定有个警察是s路口的警察，他会把s的信息返回给他的邻居，邻居再返回给邻居。最后所有的警察都知道怎么走到s,而且是最短的路:从s返回信息到所有其他点的过程就像在一个平静的池塘中从s丢下一个石头,荡起的涟漪一圈圈向外扩散，这一圈圈涟漪经过的路径肯定是最短路径

问路模型里有趣的一点 ,并且能体现Bllman-Ford思想的是警察并不需要知道到:的完整的路径,他只需要知道从自己的路口出发往哪个方向走能到达s.并且路最近

例题：http://10.64.27.5:8888/p/P34

Talk is cheap. Show me the code.

 1 #include<bits/stdc++.h>//贝尔曼福特飘过
 2 using namespace std;
 3 const int NUM=1e5;
 4 const int INF=1e6;
 5 int n,m,cnt;
 6 struct Edge
 7 {
 8     int u;//起点 
 9     int v;//终点 
10     long long  w;//权值 
11     
12 }e[NUM];//用数组存边避免了每轮操作那些等于无穷大的边 
13 int dis[NUM];//从num点到起点 的最短距离 
14 int s,t;//起点终点 
15 //int pre[NUM];
16 void bellman()
17 {
18     int start=s;
19     for(register int i=1;i<=n;i++)//初始化每个点到起点的距离是无穷 
20     {
21         dis[i]=INF;
22     }
23     dis[s]=0;// 依旧是起点 
24     for(register int i=1;i<=n;i++)//n轮操作 
25     {
26         for(register int k=0;k<cnt;k++)//cnt条边 
27         {
28             int x=e[k].u;
29             int y=e[k].v;
30             if(dis[x]>dis[y]+e[k].w)//x通过y到起点s,如果有更短，则更新 
31             dis[x]=dis[y]+e[k].w; 
32             //pre[x]=y;//前驱记录，用来打印路径的 
33         }
34     }
35     printf("%d",dis[t]);
36 }
37 int main()
38 {
39         scanf("%d %d %d %d",&n,&m,&s,&t);
40         if(n==0&&m==0)
41         return 0;
42         cnt=0;//记录边的数量，边是双向的 
43         while(m--)
44         {
45             int a,b,c;
46             scanf("%d %d %d",&a,&b,&c);
47             e[cnt].u=a;
48             e[cnt].v=b;
49             e[cnt].w=c;
50             cnt++;
51             e[cnt].u=b;
52             e[cnt].v=a;
53             e[cnt].w=c;
54             cnt++; 
55         }
56         bellman();
57     return 0;
58 }

3.传奇算法dijkstra

狄克斯特拉算法也是解决单源最短路问题，相比于前面两种算法，狄克斯特拉算法是业内公认的稳且高效的算法；

较于贝尔曼福特算法的分布式思想，狄克斯特拉算法是集中式贪心思想的典范，而对于迪克斯特拉算法，

用生活中的连锁效应和多米诺骨牌效应来理解是很贴切形象的，

而相应的实现和思想核心，也是需要去自行了解的，

对于朴素版狄克斯特拉算法，有两种优化办法：

(1)每次往B中放新数据时按从小到大的顺序放)用二分法的思路，复杂度是 O(log2n) .保证最小的数总在最前面。

(2)找最小值，直接取B的第一个数，复杂度是0(1)。

此时Dijkstra算法总的复杂度是O(mlog2n)，是最高效的最矩路径算法。

在编程时，一般不用自己写上面的程序，直接用STL的优先队列就行了,完成数据的插入和提取。

下面的程序代码中有两个关键技术:

(1)用邻接表存图和查找邻居。对邻居的查找和扩展是通过动态数组vector < edge>e[NUM]实现的邻接表，同SPFA一样。其中eL已经放到集合A中的结点不要扩展;程序中用bool done[ NUM记录集合A.当done[i=t时，表示它在集合A中，已经找到了最短路径

(2)在集合B中找距离起点最短的结点。直接用STL的优先队列实现，在程序中县 priority queue<s nodez>Q。但是有关丢弃的动作,STL的优先队列无法做到。例如需要在B=((2- -5),(2-4),6(4- -7))中丢弃(2←5),但是STL没有这种操作。在程常 中也是用bool done[NUM]协助解决这个问题。从优先队列pop出(2→4)时,记录done[27= true,表示结点2已经处理好。下次从优先队列pop出(2一5)时，判断done[ 2]是true.丢弃。i]存储第i个结点上所有的边，边的一头是它的邻居。即structedge的参数to。在需要扩展结点i的邻居的时候,查找e[i]即可。

例题http://10.64.27.5:8888/p/P34

https://www.luogu.com.cn/problem/P3371

https://www.luogu.com.cn/problem/P4779

Talk is cheap. Show me the code.

 1 #include<bits/stdc++.h>//堆优化版
 2 using namespace std;
 3 int n,m;
 4 const int NUM=1e5;
 5 const int INF=1e6;
 6 struct edge
 7 {
 8     int from;//起点 
 9     int to;//终点 
10     int w;//权值 
11     edge(int a,int b,int c)//初始化 
12     {
13         from=a;
14         to=b;
15         w=c;
16     }
17 };
18 vector<edge>e[NUM];//邻接表 
19 struct node
20 {
21     int id;//节点 
22     int d;//节点到起点的距离 
23     node(int b,int c)
24     {
25         id=b;
26         d=c;
27     }
28     bool operator<(const node &a)const//重载 
29     {
30         return d>a.d;
31     }
32 };
33 int s,t;//起点终点 
34 void dijkstra()
35 {
36     int dis[NUM];//记录所有终点到起点的距离 
37     bool done[NUM];//表示到节点i最短路径已经找到 
38     for(register int i=1;i<=n;i++)//初始化 
39     {
40         done[i]=false;
41         dis[i]=INF;
42     }
43     dis[s]=0;
44     priority_queue<node>q;//堆，优先队列 
45     q.push(node(s,dis[s]));
46     while(!q.empty())
47     {
48         node u=q.top();//距起点s最近的节点u 
49         q.pop();
50         if(done[u.id])//丢弃集合a中的找到的点 
51         continue;
52         done[u.id]=true;
53         for(register int i=0;i<e[u.id].size();i++)
54         {
55             edge y=e[u.id][i];//u.id的第i个邻居是y.to 
56             if(done[y.to])//丢弃已找到的最短路径的邻居节点 
57             continue;
58             if(dis[y.to]>y.w+u.d)
59             {
60                 dis[y.to]=y.w+u.d;
61                 q.push(node(y.to,dis[y.to]));//扩展新邻居，放在优先队列中 
62             }
63         }    
64     } 
65     printf("%d\n",dis[t]);
66 }
67 int main()
68 {
69     cin>>n>>m>>s>>t;
70     if(n==0&&m==0)
71     return 0;
72     for(register int i=1;i<=m;i++)
73     {
74         e[i].clear();
75     }
76     while(m--)
77     {
78         int a,b,c;
79         scanf("%d %d %d",&a,&b,&c);
80         e[a].push_back(edge(a,b,c));//存图 
81         e[b].push_back(edge(b,a,c));
82         
83     }
84     dijkstra();
85     return 0;
86 }

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 struct edge {
 4     int u, v, w;
 5 } edges[500001];
 6 
 7 struct node {
 8     int u, d;
 9     bool operator < (const node &n) const {
10         return d > n.d;
11     }
12 } temp;
13 
14 vector <int> map[100001];
15 priority_queue <node> q; 
16 int dis[100001]; 
17 bool visited[100001];
18 
19 int main(void) {
20     int n, m, s;
21     scanf("%d %d %d", &n, &m, &s);
22     for (int k = 1; k <= m; k++) {
23         scanf("%d %d %d", &edges[k].u, &edges[k].v, &edges[k].w);
24         map[edges[k].u].push_back(k); 
25     } 
26     memset(dis, 0x3f, sizeof(dis));
27     dis[s] = 0;
28     temp.u = s;
29     q.push(temp);
30     while (!q.empty()) {
31         node tmp = q.top();
32         q.pop();
33         if (visited[tmp.u]) {
34             continue; 
35         } 
36         visited[tmp.u] = true;
37         for (unsigned int k = 0; k < map[tmp.u].size(); k++) {
38             edge &e = edges[map[tmp.u][k]];
39             if (dis[e.v] > dis[e.u] + e.w) {
40                 temp.d = dis[temp.u = e.v] = dis[e.u] + e.w;
41                 q.push(temp);
42             }
43         }
44     }
45     for (int k = 1; k <= n; k++) {
46         printf("%d ", dis[k] == 0x3f3f3f3f ? 2147483647 : dis[k]); 
47     } 
48     return 0;
49 } 

这篇关于图论最短路算法的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！