用迪杰斯特拉算法求下图中从顶点a到其它顶点间的最短路径,要求写出执行算法过程中各步的状态,最短路径及路径长度。 a -> b (7) a -> c (2) a -> d (9) b -> c (3) b -> e (6) c -> e (8) c -> f (4) d -> c (4) d -> g (3) e -> g (9) f -> e (5) f -> g (8) f -> d (5) g -> b (4)
时间: 2023-04-12 21:01:48 浏览: 202
好的,让我来回答你的问题。根据迪杰斯特拉算法,我们需要先将起点 a 到其它顶点的距离初始化为无穷大,然后将起点 a 到自身的距离设为 0。接下来,我们需要遍历所有顶点,每次找到距离起点 a 最近的顶点,并更新其它顶点到起点 a 的距离。具体步骤如下:
1. 初始化距离数组 dist[],将 a 到其它顶点的距离设为无穷大,a 到自身的距离设为 0。
dist[a] = 0, dist[b] = ∞, dist[c] = ∞, dist[d] = ∞, dist[e] = ∞, dist[f] = ∞, dist[g] = ∞
2. 初始化 visited[],表示该顶点是否已被访问过,初始值均为 false。
visited[a] = false, visited[b] = false, visited[c] = false, visited[d] = false, visited[e] = false, visited[f] = false, visited[g] = false
3. 从未访问过的顶点中找到距离起点 a 最近的顶点,即 c,将 visited[c] 设为 true。
visited[c] = true
4. 更新其它顶点到起点 a 的距离,如果经过 c 的距离更短,则更新距离数组 dist[]。
dist[b] = 7, dist[c] = 2, dist[d] = 9, dist[e] = 10, dist[f] = 6, dist[g] = ∞
5. 重复步骤 3 和 4,找到距离起点 a 最近的未访问过的顶点 f,将 visited[f] 设为 true。
visited[f] = true
6. 更新其它顶点到起点 a 的距离,如果经过 f 的距离更短,则更新距离数组 dist[]。
dist[b] = 7, dist[c] = 2, dist[d] = 9, dist[e] = 10, dist[f] = 6, dist[g] = 11
7. 重复步骤 3 和 4,找到距离起点 a 最近的未访问过的顶点 b,将 visited[b] 设为 true。
visited[b] = true
8. 更新其它顶点到起点 a 的距离,如果经过 b 的距离更短,则更新距离数组 dist[]。
dist[b] = 7, dist[c] = 2, dist[d] = 9, dist[e] = 10, dist[f] = 6, dist[g] = 11
9. 重复步骤 3 和 4,找到距离起点 a 最近的未访问过的顶点 d,将 visited[d] 设为 true。
visited[d] = true
10. 更新其它顶点到起点 a 的距离,如果经过 d 的距离更短,则更新距离数组 dist[]。
dist[b] = 7, dist[c] = 2, dist[d] = 9, dist[e] = 10, dist[f] = 6, dist[g] = 11
11. 重复步骤 3 和 4,找到距离起点 a 最近的未访问过的顶点 e,将 visited[e] 设为 true。
visited[e] = true
12. 更新其它顶点到起点 a 的距离,如果经过 e 的距离更短,则更新距离数组 dist[]。
dist[b] = 7, dist[c] = 2, dist[d] = 9, dist[e] = 10, dist[f] = 6, dist[g] = 11
13. 重复步骤 3 和 4,找到距离起点 a 最近的未访问过的顶点 g,将 visited[g] 设为 true。
visited[g] = true
14. 更新其它顶点到起点 a 的距离,如果经过 g 的距离更短,则更新距离数组 dist[]。
dist[b] = 7, dist[c] = 2, dist[d] = 9, dist[e] = 10, dist[f] = 6, dist[g] = 11
15. 遍历结束,得到起点 a 到其它顶点的最短路径长度为:
a -> b: 7
a -> c: 2
a -> d: 9
a -> e: 10
a -> f: 6
a -> g: 11
最短路径分别为:
a -> c -> f -> e -> g -> b
a -> c
a -> d -> c -> f -> e -> g -> b
a -> c -> e
a -> f
a -> c -> f -> g -> b
阅读全文