shortest_path

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

计算图中的最短路径。

参数

G网络X图表

source节点，可选

路径的起始节点。如果未指定，则计算每个可能的起始节点的最短路径。

target节点，可选

路径的结束节点。如果未指定，则计算到所有可能节点的最短路径。

weight无、字符串或函数、可选(默认值=无)

如果没有，则每条边的权重/距离/成本为1。如果是字符串，则使用该边属性作为边权重。任何不存在的边属性默认为1。如果这是一个函数，则边的权重是该函数返回的值。该函数必须恰好接受三个位置参数：一条边的两个端点和该边的边属性字典。该函数必须返回一个数字。

method字符串，可选(默认为‘Dijkstra’)

用于计算路径的算法。支持的选项：‘Dijkstra’、‘Bellman-Ford’。其他输入会产生ValueError。如果 weight 为NONE，则使用未加权的图形方法，并忽略此建议。

返回

路径：列表或词典

所有返回的路径都包括路径中的源和目标。

如果同时指定了源和目标，则返回从源到目标的最短路径中的单个节点列表。

如果只指定了源，则返回由目标键入的字典，其中包含从源到目标的最短路径中的节点列表。

如果只指定了目标，则返回由源键控的字典，其中包含从一个源到目标的最短路径中的节点列表。

如果未指定源和目标，则返回具有路径的字典字典 [来源] [目标] = [路径中的节点列表] .

加薪

NodeNotFound

如果 source 不在 G .

ValueError

如果 method 不在支持的选项中。

参见

all_pairs_shortest_path

all_pairs_dijkstra_path

all_pairs_bellman_ford_path

single_source_shortest_path

single_source_dijkstra_path

single_source_bellman_ford_path

笔记

源和目标之间可能有多条最短路径。这只返回其中一个。

实例

>>> G = nx.path_graph(5)
>>> print(nx.shortest_path(G, source=0, target=4))
[0, 1, 2, 3, 4]
>>> p = nx.shortest_path(G, source=0)  # target not specified
>>> p[3] # shortest path from source=0 to target=3
[0, 1, 2, 3]
>>> p = nx.shortest_path(G, target=4)  # source not specified
>>> p[1] # shortest path from source=1 to target=4
[1, 2, 3, 4]
>>> p = nx.shortest_path(G)  # source, target not specified
>>> p[2][4] # shortest path from source=2 to target=4
[2, 3, 4]