Dijskra算法图解
时间: 2024-06-17 20:02:58 浏览: 13
Dijkstra算法是一种用于解决单源最短路径问题经典算法。它可以找到从一个顶点到其他所有顶点的最短路径。
下面是Dijkstra算法的图解步骤:
1. 创建一个距离数组dist[],用于存储从源顶点到其他顶点的最短距离。初始时,将源顶点的距离设置为0,其他顶点的距离设置为无穷大。
2. 创建一个集合visited[],用于记录已经找到最短路径的顶点。
3. 重复以下步骤,直到所有顶点都被访问:
a. 从未访问的顶点中选择距离最小的顶点,将其标记为visited[]。
b. 更新与该顶点相邻的顶点的最短距离。如果通过该顶点到达相邻顶点的距离比当前记录的最短距离小,则更新最短距离。
4. 最终,dist[]数组中存储的就是从源顶点到其他所有顶点的最短距离。
下面是一个简单的图解示例:
假设有以下图形:
```
2
(A)-->(B)
| \ /|
| \ / |
5| \ / |1
| \/ |
| /\ |
(C) / \ |
| / \ |
| / \|
(D)------>(E)
3
```
我们以顶点A为源顶点,开始执行Dijkstra算法:
1. 初始化dist[]数组,将A的距离设置为0,其他顶点的距离设置为无穷大。
2. 选择距离最小的顶点A,并将其标记为visited[]。
3. 更新与A相邻的顶点的最短距离:B的距离更新为2,C的距离更新为5。
4. 继续选择距离最小的未访问顶点,此时是B。
5. 更新与B相邻的顶点的最短距离:C的距离更新为3,E的距离更新为3。
6. 继续选择距离最小的未访问顶点,此时是E。
7. 更新与E相邻的顶点的最短距离:D的距离更新为6。
8. 继续选择距离最小的未访问顶点,此时是C。
9. 更新与C相邻的顶点的最短距离:D的距离更新为5。
10. 继续选择距离最小的未访问顶点,此时是D。
11. 更新与D相邻的顶点的最短距离:E的距离更新为8。
12. 所有顶点都被访问,算法结束。
最终,dist[]数组中的值为:
A: 0
B: 2
C: 3
D: 5
E: 3
相关推荐
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)