PYTHON迪杰斯特拉实例
时间: 2024-04-06 20:27:16 浏览: 9
迪杰斯特拉算法是一种用于解决图中单源最短路径问题的算法,它可以找到从一个顶点到其他所有顶点的最短路径。在Python中,可以使用图的邻接矩阵或邻接表来实现迪杰斯特拉算法。
以下是一个使用邻接矩阵实现迪杰斯特拉算法的Python示例:
```python
import sys
# 定义一个函数来找到未被访问的顶点中距离最小的顶点
def find_min_distance(distances, visited):
min_distance = sys.maxsize
min_index = -1
for v in range(len(distances)):
if distances[v] < min_distance and not visited[v]:
min_distance = distances[v]
min_index = v
return min_index
# 使用迪杰斯特拉算法找到从起点到其他所有顶点的最短路径
def dijkstra(graph, start):
num_vertices = len(graph)
distances = [sys.maxsize] * num_vertices # 存储起点到每个顶点的最短距离
visited = [False] * num_vertices # 记录顶点是否已被访问
distances[start] = 0 # 起点到自身的距离为0
for _ in range(num_vertices):
u = find_min_distance(distances, visited)
visited[u] = True
for v in range(num_vertices):
if (
graph[u][v] > 0
and not visited[v]
and distances[u] + graph[u][v] < distances[v]
):
distances[v] = distances[u] + graph[u][v]
return distances
# 示例图的邻接矩阵表示
graph = [
[0, 4, 0, 0, 0, 0, 0, 8, 0],
[4, 0, 8, 0, 0, 0, 0, 11, 0],
[0, 8, 0, 7, 0, 4, 0, 0, 2],
[0, 0, 7, 0, 9, 14, 0, 0, 0],
[0, 0, 0, 9, 0, 10, 0, 0, 0],
[0, 0, 4, 14, 10, 0, 2, 0, 0],
[0, 0, 0, 0, 0, 2, 0, 1, 6],
[8, 11, 0, 0, 0, 0, 1, 0, 7],
[0, 0, 2, 0, 0, 0, 6, 7, 0],
]
start_vertex = 0
shortest_distances = dijkstra(graph, start_vertex)
# 输出从起点到其他顶点的最短距离
for v in range(len(graph)):
print(f"从顶点 {start_vertex} 到顶点 {v} 的最短距离为: {shortest_distances[v]}")
```