rustworkx.single_source_all_shortest_paths#

single_source_all_shortest_paths(graph, source, weight_fn=None, default_weight=1.0, as_undirected=False)[source]#

从单个源点到所有其他节点的所有最短路径。

此函数将使用 Dijkstra 算法生成从源节点到所有其他节点的所有可能最短路径。 如果对有向图，as_undirected 为 True，则会将其视为无向图。

Parameters:

  • graph – 输入图 PyGraph 或 PyDiGraph.

  • source (int) – 要查找路径的源节点索引。

  • weight_fn – 一个可选的计算边权重的函数。该函数将接受一个参数，即边的权重对象，并返回一个浮点数，该浮点数将用于表示边的权重/成本。

  • default_weight (float) – 如果未指定 weight_fn，此可选浮点值将用于每条边的权重/成本。

  • as_undirected (bool) – 如果为真，将有向图视为无向图（仅适用于 PyDiGraph）。

Returns:

一个字典，其中键是节点索引，值为从源节点到该节点的所有最短路径。每条路径都是以源节点开头的节点索引列表。

Return type:

字典

Raises:

  • ValueError – when an edge weight with NaN or negative value is provided.

  • 索引错误 – 若源节点索引超出范围。

警告

该函数在特定图中可能返回指数级数量的路径，尤其当存在零权重边时。 对于大多数使用场景，建议考虑使用dijkstra_shortest_paths来获取单条最短路径，其运行速度会快得多。