python单源最短路径

在Python的NetworkX库中，可以使用nx.shortest_path()函数来计算有向或无向带权图中的单源最短路径。该函数的语法如下：

nx.shortest_path(G, source, target=None, weight=None, method='dijkstra')

其中，参数说明如下：
- G：图形对象，可以是有向图或无向图。
- source：源节点，表示起始节点。
- target：目标节点，表示终止节点。如果未指定，则计算源节点到图中所有其他节点的最短路径。
- weight：边的权重属性的名称。如果图中的边没有权重属性，则默认为None。
- method：计算最短路径的方法。可选的方法有'dijkstra'（迪杰斯特拉算法）和'bellman-ford'（贝尔曼-福特算法）。默认为'dijkstra'。

下面是一个示例，演示如何使用nx.shortest_path()函数计算有向图中的单源最短路径：

import networkx as nx

# 创建有向图
G = nx.DiGraph()

# 添加边和权重
G.add_edge('A', 'B', weight=3)
G.add_edge('A', 'C', weight=5)
G.add_edge('B', 'C', weight=2)
G.add_edge('B', 'D', weight=6)
G.add_edge('C', 'D', weight=4)
G.add_edge('D', 'E', weight=1)

# 计算从节点'A'到节点'E'的最短路径
shortest_path = nx.shortest_path(G, 'A', 'E', weight='weight')
print("Shortest path:", shortest_path)  # 输出：['A', 'B', 'C', 'D', 'E']

这段代码创建了一个有向图，并添加了边和权重。然后，使用nx.shortest_path()函数计算从节点'A'到节点'E'的最短路径，并将结果打印出来。