最短路径

计算图中节点之间的最短路径和路径长度。

这些算法适用于无向图和有向图。

shortest_path (g) [, source, target, weight, ...] )

计算图中的最短路径。

all_shortest_paths \(G,源,目标[, ...] )

计算图中的所有最短路径。

shortest_path_length (g) [, source, target, ...] )

计算图中的最短路径长度。

average_shortest_path_length (g) [, weight, method] )

返回平均最短路径长度。

has_path \(G,源,目标)

返回 True 如果 G 有一条来自 来源目标 .

高级接口

无权重图的最短路径算法。

single_source_shortest_path (g,源) [, cutoff] )

计算源和所有其他可以从源访问的节点之间的最短路径。

single_source_shortest_path_length \(G,来源)

计算从源到所有可到达节点的最短路径长度。

single_target_shortest_path (g,目标) [, cutoff] )

从到达目标的所有节点计算到目标的最短路径。

single_target_shortest_path_length \(G,目标)

计算从所有可到达节点到目标的最短路径长度。

bidirectional_shortest_path \(G,源,目标)

返回源和目标之间最短路径中的节点列表。

all_pairs_shortest_path (g) [, cutoff] )

计算所有节点之间的最短路径。

all_pairs_shortest_path_length (g) [, cutoff] )

计算中所有节点之间的最短路径长度 G .

predecessor (g,源) [, target, cutoff, ...] )

返回g中从源到所有节点的路径的前置任务的dict

加权图的最短路径算法。

dijkstra_predecessor_and_distance \(G,来源)

计算加权最短路径长度和前置任务。

dijkstra_path \(G,源,目标[, weight] )

返回从源到目标的最短加权路径(g)。

dijkstra_path_length \(G,源,目标[, weight] )

返回从源到目标的最短加权路径长度(g)。

single_source_dijkstra (g,源) [, target, ...] )

从源节点查找最短的加权路径和长度。

single_source_dijkstra_path (g,源) [, ...] )

从源节点找到G中最短的加权路径。

single_source_dijkstra_path_length \(G,来源)

从源节点找到以g为单位的最短加权路径长度。

multi_source_dijkstra \(G,来源[, target, ...] )

从给定的一组源节点中查找最短的加权路径和长度。

multi_source_dijkstra_path \(G,来源[, ...] )

从给定的一组源节点中找到以g为单位的最短加权路径。

multi_source_dijkstra_path_length \(G,来源)

从给定的一组源节点中找到以g为单位的最短加权路径长度。

all_pairs_dijkstra (g) [, cutoff, weight] )

在所有节点之间找到最短的加权路径和长度。

all_pairs_dijkstra_path (g) [, cutoff, weight] )

计算加权图中所有节点之间的最短路径。

all_pairs_dijkstra_path_length (g) [, cutoff, ...] )

计算加权图中所有节点之间的最短路径长度。

bidirectional_dijkstra \(G,源,目标[, ...] )

使用双向搜索的Dijkstra最短路径算法。

bellman_ford_path \(G,源,目标[, weight] )

返回加权图G中从源到目标的最短路径。

bellman_ford_path_length \(G,源,目标)

返回加权图中从源到目标的最短路径长度。

single_source_bellman_ford (g,源) [, ...] )

在加权图G中计算最短路径和长度。

single_source_bellman_ford_path (g,源) [, ...] )

计算加权图的源节点和所有其他可到达节点之间的最短路径。

single_source_bellman_ford_path_length \(G,来源)

计算加权图的源节点和所有其他可到达节点之间的最短路径长度。

all_pairs_bellman_ford_path (g) [, weight] )

计算加权图中所有节点之间的最短路径。

all_pairs_bellman_ford_path_length (g) [, weight] )

计算加权图中所有节点之间的最短路径长度。

bellman_ford_predecessor_and_distance \(G,来源)

计算加权图中最短路径的最短路径长度和最短路径上的前置任务。

negative_edge_cycle (g) [, weight] )

如果g中的任何地方存在负的边循环,则返回true。

goldberg_radzik (g,源) [, weight] )

计算加权图中最短路径的最短路径长度和最短路径上的前置任务。

johnson (g) [, weight] )

使用约翰逊算法计算最短路径。

稠密图

最短路径的Floyd Warshall算法。

floyd_warshall (g) [, weight] )

使用Floyd算法查找所有对的最短路径长度。

floyd_warshall_predecessor_and_distance (g) [, ...] )

使用Floyd算法查找所有对的最短路径长度。

floyd_warshall_numpy (g) [, nodelist, weight] )

使用Floyd算法查找所有对的最短路径长度。

reconstruct_path \(源,目标,前置任务)

使用Floyd_Warshall_Previous_and_Distance返回的前辈dict重建从源到目标的路径

A*算法

使用A*(“A星”)算法的最短路径和路径长度。

astar_path \(G,源,目标[, heuristic, ...] )

使用a*(a-star)算法返回源和目标之间最短路径中的节点列表。

astar_path_length \(G,源,目标[, ...] )

使用A*(“A星”)算法返回源和目标之间最短路径的长度。