Shortest Paths

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

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

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)	返回 True 如果 G 从 source 到 target 存在路径。

Advanced Interface

无权图的最短路径算法。

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中所有节点的路径的前驱节点字典。

加权图的最短路径算法。

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算法计算最短路径。

Dense Graphs

弗洛伊德-沃舍尔算法用于最短路径。

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* Algorithm

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

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