最短路径-Dijkstra+Floyd

时间：2019-03-24 10:51:11 阅读：121 评论：0 收藏：0 [点我收藏+]

Dijkstra算法：

Dijkstra(迪杰斯特拉)算法是典型的单源最短路径算法，用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。Dijkstra算法是很有代表性的最短路径算法，在很多专业课程中都作为基本内容有详细的介绍，如数据结构，图论，运筹学等等。注意该算法要求图中不存在负权边。

问题描述：在无向图 G=(V,E) 中，假设每条边 E[i] 的长度为 w[i]，找到由顶点 V0 到其余各点的最短路径。（单源最短路径）

算法的基本思想是：每次找到离源点（上面例子的源点就是 1 号顶点）最近的一个顶点，然后以该顶点为中心进行扩展，最终得到源点到其余所有点的最短路径。基本步骤如下：

将所有的顶点分为两部分：已知最短路程的顶点集合 P 和未知最短路径的顶点集合 Q。最开始，已知最短路径的顶点集合 P 中只有源点一个顶点。我们这里用一个vis[i]数组来记录哪些点在集合 P 中。例如对于某个顶点 i，如果vis[i]为 1 则表示这个顶点在集合 P 中，如果 vis [i]为 0 则表示这个顶点在集合 Q 中。
设置源点 s 到自己的最短路径为 0 即 dis=0。若存在源点有能直接到达的顶点 i，则把 dist[ i ]设为 e[s][i]。同时把所有其它（源点不能直接到达的）顶点的最短路径为设为 ∞。
在集合 Q 的所有顶点中选择一个离源点 s 最近的顶点 u（即 dist[u]最小）加入到集合 P。并考察所有以点 u 为起点的边，对每一条边进行松弛操作。例如存在一条从 u 到 v 的边，那么可以通过将边 u->v 添加到尾部来拓展一条从 s 到 v 的路径，这条路径的长度是 dist[u]+e[u][v]。如果这个值比目前已知的 dist[v]的值要小，我们可以用新值来替代当前 dist[v]中的值。
重复第 3 步，如果集合 Q 为空，算法结束。最终 dist 数组中的值就是源点到所有顶点的最短路径。

技术分享图片

Floyd算法:

Floyd算法又称为插点法，理解起来也很方便，复杂度为o(n³)，如要从结点1到结点n，可以由1直通n，再逐渐向其中插入其他结点作为中转点，不断更新在插入结点后的最短路径。

代码也很简洁，四行的算法。

 for(int i=1;i<=n;i++)
    for(int j=1;j<=n;j++)
    for(int k=1;k<=n;k++)
    e[j][k]=min(e[j][i]+e[i][k],e[j][k]);

HDU-3790 最短路径（模板题）

Dijkstra版：

这个算法还能利用堆和优先队列进行优化（但是我不会

下面是没有任何优化的最简单版本

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll;
 4 typedef unsigned long long ull;
 5 #define INF 0X3f3f3f3f
 6 const ll MAXN = 1e3 + 7;
 7 const ll mod = 1e9 + 7;
 8 //权值为正
 9 int n, m;
10 int vis[MAXN];
11 int dist[MAXN];
12 int a[MAXN][MAXN];
13 void Dijkstra(int x,int y)
14 {
15     for (int i = 1; i <= n; i++)
16     {
17         dist[i] = a[x][i];
18         vis[i] = 0;
19     }
20     vis[x] = 1;
21     int p;
22     for (int i = 1; i <= n; i++)
23     {
24         int minn = INF;
25         for (int j = 1; j <= n; j++)
26         {
27             if (!vis[j] && dist[j] < minn)
28             {   
29                 minn = dist[j];
30                 p = j;
31             }
32         }
33         vis[p] = 1;
34         for (int j = 1; j <= n; j++)
35             if (!vis[j] && dist[p] + a[p][j] < dist[j])
36                 dist[j] = dist[p] + a[p][j];//更新这个找到的距离最小的点所连的点的距离 
37     }
38 }
39 int main()
40 {
41     ios::sync_with_stdio(false);
42     while (cin >> n >> m && n && m)
43     {
44         memset(a,INF,sizeof(a));
45         for (int i = 0; i < m; i++)
46         {
47             int x, y, len;
48             cin >> x >> y >> len;
49             a[x][y] = len;
50             a[y][x] = len; //无向图
51         }
52         Dijkstra(1,n);
53         cout << dist[n] << endl;
54     }
55 }

Dijkstra版本

Floyd版：

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll;
 4 typedef unsigned long long ull;
 5 #define INF 0X3f3f3f3f
 6 const ll MAXN = 1e3 + 7;
 7 const ll mod = 1e9 + 7;
 8 //可处理权值为负的情况
 9 int n,m;
10 int e[MAXN][MAXN];
11 void floyd()
12 {
13     for(int i=1;i<=n;i++)
14     for(int j=1;j<=n;j++)
15     for(int k=1;k<=n;k++)
16     e[j][k]=min(e[j][i]+e[i][k],e[j][k]);
17 }
18 int main()
19 {
20     while(cin>>n>>m&&n&&m)
21     {
22         memset(e,INF,sizeof(e));
23         for(int i=0;i<m;i++)
24         {
25             int a,b,c;
26             cin>>a>>b>>c;
27             e[a][b]=c;
28             e[b][a]=c;
29         }
30         floyd();
31         cout<<e[1][n]<<endl;
32     }
33     return 0;
34 }

Floyd版

最短路径-Dijkstra+Floyd

原文：https://www.cnblogs.com/graytido/p/10587084.html

踩

(0)

评论一句话评论（0）

分享档案

更多>

2021年09月23日 (328)
2021年09月24日 (313)
2021年09月17日 (191)
2021年09月15日 (369)
2021年09月16日 (411)
2021年09月13日 (439)
2021年09月11日 (398)
2021年09月12日 (393)
2021年09月10日 (160)
2021年09月08日 (222)