迪杰斯特拉算法的案例
时间: 2023-12-10 12:34:24 浏览: 26
以下是一个使用迪杰斯特拉算法求解最短路径的案例:
假设有一个无向图,其中包含6个节点和9条边,每条边都有对应的权重。节点之间的连线关系如下图所示:
![image](https://user-images.githubusercontent.com/52498280/129448764-7d5c8f3e-4b5d-4d5d-9d5a-9d7d7d7d7d7d.png)
现在需要求出节点A到其他节点的最短路径。
首先,初始化距离数组dist和标记数组visited,将起始节点A的距离设为0,其他节点的距离设为无穷大,将所有节点的visited标记设为False。
然后,从起始节点A开始,依次遍历与其相邻的节点,并更新它们的距离值。具体步骤如下:
1. 从dist数组中找到距离起始节点A最近的节点B,将B的visited标记设为True。
2. 遍历与节点B相邻的节点C,如果C的visited标记为False,计算从起始节点A到C的距离,如果该距离小于dist数组中C的距离值,则更新dist数组中C的距离值。
3. 重复步骤1和步骤2,直到所有节点的visited标记都为True。
最终,dist数组中存储的就是起始节点A到其他节点的最短路径。
以下是Python代码实现:
```python
import sys
# 无穷大
INF = sys.maxsize
# 无向图的邻接矩阵表示
graph = [
[0, 7, 9, INF, INF, 14],
[7, 0, 10, 15, INF, INF],
[9, 10, 0, 11, INF, 2],
[INF, 15, 11, 0, 6, INF],
[INF, INF, INF, 6, 0, 9],
[14, INF, 2, INF, 9, 0]
]
# 节点个数
n = len(graph)
# 起始节点
start = 0
# 初始化距离数组和标记数组
dist = [INF] * n
visited = [False] * n
dist[start] = 0
# 迪杰斯特拉算法
for i in range(n):
# 找到距离起始节点最近的节点
min_dist = INF
min_index = -1
for j in range(n):
if not visited[j] and dist[j] < min_dist:
min_dist = dist[j]
min_index = j
visited[min_index] = True
# 更新与该节点相邻的节点的距离值
for k in range(n):
if not visited[k] and graph[min_index][k] != INF:
new_dist = dist[min_index] + graph[min_index][k]
if new_dist < dist[k]:
dist[k] = new_dist
# 输出起始节点到其他节点的最短路径
for i in range(n):
if i != start:
print("从节点{}到节点{}的最短路径为:{}".format(chr(start+65), chr(i+65), dist[i]))
```
相关推荐
![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)
![](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)
![](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)