python - 如何为未加权图做最短路径算法？

Question

我试图找到从一个顶点到另一个连接的未加权图形的最短路径。

在这个问题中，从一个顶点到它的相邻顶点的距离将等于 1。即，如果考虑具有边 (a,b),(a,c) 的图，从 a 到 b 的距离c 为 1，b 到 c 的距离为 2。此外，还维护了一个邻接表来存储每个顶点的所有相邻顶点。

那么，有没有算法可以找到给定问题的所有最短路径？？

Answer 1

您可以使用 dijkstra 算法来计算距离。

这是使用 networkx

的一种方法

In [28]: import networkx as nx

创建一个带有节点 a, b, c 的 grpah，其中链接是 a, b 和 'a, c'

In [29]: g = nx.Graph()

In [30]: g.add_edge('a', 'b')

In [31]: g.add_edge('a', 'c')

然后使用nx.dijkstra_path_length() 找到b 和c 之间的距离

In [32]: nx.dijkstra_path_length(g, 'b', 'c')
Out[32]: 2

此外，您可以使用 dijkstra_path()

找到路径轨迹

In [33]: nx.dijkstra_path(g, 'b', 'c')
Out[33]: ['b', 'a', 'c']

您还可以使用 shortest_path() 作为 b 和 c 之间的路径>

In [34]: nx.shortest_path(g, source='b',target='c')
Out[34]: ['b', 'a', 'c']