请用Python程序语言求给定正权有向图的单源最短路径长度。图中包含 n 个顶点,编号为0至n−1,以顶点0作为源点,计算源点到各个顶点的最短路径长度。
时间: 2024-10-18 11:07:33 浏览: 43
在Python中,我们可以使用Dijkstra算法来求解这个问题。Dijkstra算法是一种用于寻找带权重有向图中两个节点之间最短路径的算法。以下是使用`networkx`库实现的一个简单示例:
```python
import networkx as nx
# 假设我们有一个字典表示图的邻接权重
graph = {
'0': {'1': 3, '2': 5},
'1': {'2': 1, '3': 4},
'2': {'3': 2},
'3': {}
}
def dijkstra(graph, source):
distances = {node: float('infinity') for node in graph}
distances[source] = 0
shortest_path = {}
visited = set()
while not visited == set(distances.keys()):
min_distance_node = None
for node, distance in distances.items():
if node not in visited and (min_distance_node is None or distance < distances[min_distance_node]):
min_distance_node = node
if min_distance_node is None:
break
visited.add(min_distance_node)
for neighbor, weight in graph[min_distance_node].items():
new_distance = distances[min_distance_node] + weight
if new_distance < distances[neighbor]:
distances[neighbor] = new_distance
shortest_path[neighbor] = min_distance_node
return distances, shortest_path
shortest_distances, path = dijkstra(graph, 0)
print("源点0到各顶点的最短距离:")
for vertex, dist in shortest_distances.items():
print(f"顶点{vertex}: {dist}")
print("\n从源点0到每个顶点的最短路径:")
for dest, src in path.items():
print(f"从0到{dest}的路径: {src}->{dest}")
阅读全文