最短路径

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

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

shortest_path(G[, source, target, weight, ...])	计算图中的最短路径。
all_shortest_paths(G, source, target[, ...])	计算图中的所有最短简单路径。
all_pairs_all_shortest_paths(G[, weight, method])	计算所有节点之间的所有最短路径。
single_source_all_shortest_paths(G, source)	计算图中从给定源节点到所有节点的所有最短简单路径。
shortest_path_length(G[, source, target, ...])	计算图中的最短路径长度。
average_shortest_path_length(G[, weight, method])	返回平均最短路径长度。
has_path(G, source, target)	如果 G 中存在从源节点到目标节点的路径，则返回 True。

高级接口

无权图的最短路径算法。

single_source_shortest_path(G, source[, cutoff])	计算从源节点到所有可达节点的 shortest path。
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 中从源节点到所有节点的路径上的前驱节点字典。

加权图的最短路径算法。

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])	使用 Johnson 算法计算最短路径。

密集图

用于最短路径的 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_predecessor_and_distance 返回的前驱节点字典重构从源节点到目标节点的路径。

A* 算法

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

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