常见的最短路径算法一般有Floyd,Dijkstra,Johnson,Bellman-Ford算法。按照课本所学的先后顺序,我们先讲Dijkstra。
Dijkstra算法
Dijkstra算法其实是Floyd的优化,成功将$O(n^3)$降到了$O(n^2)$,并且还是采用了动态规划的思想。我们从起点枚举最短路径开始。
比如从A出发,我们会知道首先选择B,其路径为$A\rightarrow B:1$。好的接下来哪个路径最短?首先不能是A到D吧,边权都3了。那应该是2吗?好像是吧。。。
其实不妨这么想,在找到路径之后,都更新路径数组dp[],这里可以看到,若要A到C,可以选择$A\rightarrow C$,也可以$A\rightarrow B \rightarrow C$,但其实$A\rightarrow C$更短。
所以有了如下的状态转移方程;
其中$i$是可联通顶点,$now$是刚刚找到的最短路终顶点,$dp[i]$是起点到顶点$i$的最短路径。
暴力解法:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
| void dijkstra(int s) { dis = adjmat[s]; visit[s] = true; for (int i = 1; i < n; i++) { int minW = INT_MAXN, now = -1; for (int j = 0; j < n; j++) { if (!visit[j] && dis[j] <= minW) { minW = dis[j]; now = j; } } if (now == -1) return; visit[now] = true; for (int j = 0; j < n; j++) { if (!visit[j]) dis[j] = min(dis[j], dis[now] + adjmat[now][j]); } } for (auto i: dis) cout << i << ' '; }
|
下面是输出路径版本:
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
| void dijkstra(int s) { dis = adjmat[s]; visit[s] = true; for(int i = 0; i < n; i++) parent[i] = i; for (int i = 1; i < n; i++) { int minW = INT_MAXN, now = -1; for (int j = 0; j < n; j++) { if (!visit[j] && dis[j] <= minW) { minW = dis[j]; now = j; } } if (now == -1) return; visit[now] = true; for (int j = 0; j < n; j++) { if (!visit[j] && dis[now] + adjmat[now][j] < dis[j]) { dis[j] = dis[now] + adjmat[now][j]; parent[j] = now; } } } for (auto i: dis) cout << i << ' '; cout << endl; for (int i = 1; i < parent.size(); i++) { cout << s << "->" << i << " is " << dis[i] << ": 0--"; int j = i; while (j != parent[j]) { cout << parent[j] << "--"; j = parent[j]; } cout << i << endl; } }
|