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

Question

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

在这个问题中，一个顶点到它的相邻顶点的距离将等于1.ie。如果考虑一个有边(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 and 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 and c

之间的路径

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

Answer 2

你可以用一个函数找到所有的路径，然后选择长度最小的路径。

但请注意，此问题更多是基于您的搜索算法，例如使用 BFS 算法：

您可以使用 following function return 路径生成器 :

def all_paths(graph, start, goal):
    queue = [(start, [start])]
    while queue:
        (v, path) = queue.pop(0)
        for next in graph[v] - set(path):
            if next == goal:
                yield path + [next]
            else:
                queue.append((next, path + [next]))

并找到以len为键的min函数的最小路径：

min_path = min(all_paths(graph, start, goal),key=len)

Answer 3

从那时起您可以使用 BFS：http://en.wikipedia.org/wiki/Breadth-first_search

如果时间不是问题并且您想要简单，您还可以使用运行 O(n^3) 的 Floyd–Warshall 算法：http://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm

Answer 4

Dijkstra算法求解"the problem of finding a path between two vertices (or nodes) in a graph such that the sum of the weights of its constituent edges is minimized".

http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm

因此，我认为您可以使用 Dijkstra 解决此问题，其中对于两个顶点之间的每条路径，从一个顶点到其相邻顶点的距离都相等。

无论如何，你可以使用 BFS http://en.wikipedia.org/wiki/Breadth-first_search

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

How to do shortest path algorithm for unweighted graph?

python

algorithm

graph

shortest-path