最短路径问题举例并求解
时间: 2024-03-14 13:47:30 浏览: 16
假设有如下的有向带权图,其中顶点 1 到顶点 6 的编号依次为 1, 2, 3, 4, 5, 6,权重表示在两个顶点之间移动的代价:
```
2
(1)------>(2)
/ \ |
3/ \1 |2
/ \ |
v v v
(3)---->(4)-->(5)
\ /1 |1
4\ / |
v v v
(6)------>(7)
3
```
我们要求顶点 1 到顶点 7 的最短路径。
使用 Dijkstra 算法求解:
1. 初始化起点到各个顶点的距离为无穷大,起点到自身的距离为 0。
```
dist[1] = 0
dist[2] = inf
dist[3] = inf
dist[4] = inf
dist[5] = inf
dist[6] = inf
dist[7] = inf
```
2. 从起点开始,依次扩展距离最短的顶点。
```
1. dist[2] = 2, prev[2] = 1
2. dist[3] = 3, prev[3] = 1
3. dist[4] = 4, prev[4] = 2
4. dist[5] = 6, prev[5] = 4
5. dist[6] = 7, prev[6] = 3
6. dist[7] = 10, prev[7] = 5
```
3. 最短路径为 1 -> 2 -> 4 -> 5 -> 7,距离为 10。
使用 Bellman-Ford 算法求解:
1. 初始化起点到各个顶点的距离为无穷大,起点到自身的距离为 0。
```
dist[1] = 0
dist[2] = inf
dist[3] = inf
dist[4] = inf
dist[5] = inf
dist[6] = inf
dist[7] = inf
```
2. 重复 n-1 次以下操作,其中 n 是顶点的个数:
1. 对于每条边 (u, v),如果 dist[u] + w(u, v) < dist[v],则更新 dist[v] = dist[u] + w(u, v)。
```
1. dist[2] = 2, prev[2] = 1
2. dist[3] = 3, prev[3] = 1
3. dist[4] = 4, prev[4] = 2
4. dist[5] = 6, prev[5] = 4
5. dist[6] = 7, prev[6] = 3
6. dist[7] = 10, prev[7] = 5
```
3. 最短路径为 1 -> 2 -> 4 -> 5 -> 7,距离为 10。
因为该图没有负权环,所以 Dijkstra 算法和 Bellman-Ford 算法得到的结果是相同的。