朴素 Dijkstra 算法
算法框架
算法步骤
适用于稠密图，故用邻接矩阵存储图
st[]存储所有当前已经更新过其他点的点。
1、遍历 $n$ 次，找到当前不在st集合中的，距离起点最近的点，赋给t
2、用t去更新其他所有能够直连的点的距离：dist[x] > dist[t] + w若真，就更新dist[x]。
证明
基于贪心，无需掌握，过程略。
提示
每一轮迭代，在还没有更新过其他点的所有点中，找到距离起点最近的点t，然后用t去更新其他所有点到起点的距离。
1
2
3
4
| int t = -1; // 为了方便找这样一个距离起点最近的点，先让 t = -1，以便加入起点循环查找
for (int j = 1; j <= n; j ++ )
if (!st[j] && (t == -1 || dist[t] > dist[j]))
t = j;
|
完整代码
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
| #include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 510;
int n, m;
int g[N][N];
int dist[N]; // 当前点到初始点的最短距离
bool st[N]; // st数组更确切的含义是某个点是否已经更新过其他点，而不是它的最短距离是否已经确定
int dijkstra()
{
memset(dist, 0x3f, sizeof dist);
dist[1] = 0;
for (int i = 0; i < n; i ++ )
{
int t = -1;
for (int j = 1; j <= n; j ++ )
if (!st[j] && (t == -1 || dist[t] > dist[j]))
t = j;
st[t] = true;
// 实际上，这里也只用t去更新了其他与t相邻的点的距离，只更新了相邻节点，因为不是相邻的话
// g[t][j] 为 INF，相当于没有更新。
for (int j = 1; j <= n; j ++ )
dist[j] = min(dist[j], dist[t] + g[t][j]); // 用t去更新其他点的距离
}
if (dist[n] == 0x3f3f3f3f) return -1;
return dist[n];
}
int main()
{
cin >> n >> m;
memset(g, 0x3f, sizeof g);
while (m -- )
{
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
g[a][b] = min(g[a][b], c); // 处理自环和重边
}
int t = dijkstra();
cout << t << endl;
return 0;
}
|
Python3
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
| N, M = 510, int(1e5 + 10)
dist = [0 for _ in range(N)]
st = [False for _ in range(N)]
g = [[0] * N for _ in range(N)]
def dijkstra():
dist = [int(1e9) for _ in range(N)]
dist[1] = 0
for i in range(n):
t = -1
for j in range(1, n + 1):
if not st[j] and (t == -1 or dist[t] > dist[j]):
t = j
st[t] = True
for j in range(1, n + 1):
dist[j] = min(dist[j], dist[t] + g[t][j])
if dist[n] == int(1e9): return -1
return dist[n]
if __name__ == '__main__':
n, m = map(int, input().split())
g = [[int(1e9)] * N for _ in range(N)]
while m:
m -= 1
a, b, c = map(int, input().split())
g[a][b] = min(g[a][b], c)
print(dijkstra())
|
支付宝
微信