如何为未加权图做最短路径算法？
我试图找到从顶点到另一个连接的未加权图形的最短路径。
在这个问题中，如果考虑具有边（a，b），（a，c）的图，则从顶点到其相邻顶点的距离将等于1.ie。从a到b和c的距离将会为1并且从b到c的距离将为2.此外，维护邻接列表以存储每个顶点的所有相邻顶点。
那么，是否有任何算法可以找到给定问题的所有最短路径？
你可以使用dijkstra的算法来找到距离。
这是使用networkx的一种方法
In [28]: import networkx as nx
创建节点a, b, c的grpah a, b, c其中链接是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']
你也可以在b and c之间使用shortest_path()
In [34]: nx.shortest_path(g, source='b',target='c')
Out[34]: ['b', 'a', 'c']
你可以找到所有具有函数的路径，然后选择具有最小长度的路径。
但请注意，此问题更多基于您的搜索算法，例如使用BFS算法：
您可以使用以下返回路径生成器的函数：
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)
您可以从这一点使用BFS：http：//en.wikipedia.org/wiki/Breadth-first_search
如果时间不是问题并且您想要简单，您也可以使用运行O（n ^ 3）的Floyd-Warshall算法：http://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm
链接地址: http://www.djcxy.com/p/35303.html上一篇: How to do shortest path algorithm for unweighted graph?