最短路径

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

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

shortest_path(G[, source, target, weight, ...])	计算图中的最短路径。
all_shortest_paths(G, source, target[, ...])	计算图中所有最短的简单路径。
shortest_path_length(G[, source, target, ...])	计算图中的最短路径长度。
average_shortest_path_length(G[, weight, method])	返回平均最短路径长度。
has_path(G, source, target)	返回 True 如果 G 有一条来自 来源 到 目标 .

高级接口

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

single_source_shortest_path(G, source[, cutoff])	计算源和所有其他可以从源访问的节点之间的最短路径。
single_source_shortest_path_length(G, source)	计算从源到所有可到达节点的最短路径长度。
single_target_shortest_path(G, target[, cutoff])	从到达目标的所有节点计算到目标的最短路径。
single_target_shortest_path_length(G, target)	计算从所有可到达节点到目标的最短路径长度。
bidirectional_shortest_path(G, source, target)	返回源和目标之间最短路径中的节点列表。
all_pairs_shortest_path(G[, cutoff])	计算所有节点之间的最短路径。
all_pairs_shortest_path_length(G[, cutoff])	计算中所有节点之间的最短路径长度 G .
predecessor(G, source[, target, cutoff, ...])	返回g中从源到所有节点的路径的前置任务的dict

加权图的最短路径算法。

dijkstra_predecessor_and_distance(G, source)	计算加权最短路径长度和前置任务。
dijkstra_path(G, source, target[, weight])	返回从源到目标的最短加权路径（g）。
dijkstra_path_length(G, source, target[, weight])	返回从源到目标的最短加权路径长度（g）。
single_source_dijkstra(G, source[, target, ...])	从源节点查找最短的加权路径和长度。
single_source_dijkstra_path(G, source[, ...])	从源节点找到G中最短的加权路径。
single_source_dijkstra_path_length(G, source)	从源节点找到以g为单位的最短加权路径长度。
multi_source_dijkstra(G, sources[, target, ...])	从给定的一组源节点中查找最短的加权路径和长度。
multi_source_dijkstra_path(G, sources[, ...])	从给定的一组源节点中找到以g为单位的最短加权路径。
multi_source_dijkstra_path_length(G, sources)	从给定的一组源节点中找到以g为单位的最短加权路径长度。
all_pairs_dijkstra(G[, cutoff, weight])	在所有节点之间找到最短的加权路径和长度。
all_pairs_dijkstra_path(G[, cutoff, weight])	计算加权图中所有节点之间的最短路径。
all_pairs_dijkstra_path_length(G[, cutoff, ...])	计算加权图中所有节点之间的最短路径长度。
bidirectional_dijkstra(G, source, target[, ...])	使用双向搜索的Dijkstra最短路径算法。
bellman_ford_path(G, source, target[, weight])	返回加权图G中从源到目标的最短路径。
bellman_ford_path_length(G, source, target)	返回加权图中从源到目标的最短路径长度。
single_source_bellman_ford(G, source[, ...])	在加权图G中计算最短路径和长度。
single_source_bellman_ford_path(G, source[, ...])	计算加权图的源节点和所有其他可到达节点之间的最短路径。
single_source_bellman_ford_path_length(G, source)	计算加权图的源节点和所有其他可到达节点之间的最短路径长度。
all_pairs_bellman_ford_path(G[, weight])	计算加权图中所有节点之间的最短路径。
all_pairs_bellman_ford_path_length(G[, weight])	计算加权图中所有节点之间的最短路径长度。
bellman_ford_predecessor_and_distance(G, source)	计算加权图中最短路径的最短路径长度和最短路径上的前置任务。
negative_edge_cycle(G[, weight, heuristic])	如果g中的任何地方存在负的边循环，则返回true。
find_negative_cycle(G, source[, weight])	返回总权重为负的循环(如果存在)。
goldberg_radzik(G, source[, 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(source, target, predecessors)	使用Floyd_Warshall_Previous_and_Distance返回的前辈dict重建从源到目标的路径

A*算法

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

astar_path(G, source, target[, heuristic, ...])	使用a*（a-star）算法返回源和目标之间最短路径中的节点列表。
astar_path_length(G, source, target[, ...])	使用A*（“A星”）算法返回源和目标之间最短路径的长度。