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

我试图找到从顶点到另一个连接的未加权图形的最短路径。如何为未加权图做最短路径算法？

在这个问题中，如果考虑具有边（a，b），（a，c）的图，则从顶点到其相邻顶点的距离将等于1.ie，距离a到b和c将为1，从b到c的距离为2. 此外，维护一个邻接表以存储每个顶点的所有相邻顶点。

那么，是否有任何算法找到给定问题的所有最短路径？

2015-05-02 Gayathri BS

可能重复（http://stackoverflow.com/questions/1846836/the-best-shortest-path-algorithm） – DTing

您可以使用dijkstra的算法来查找距离。

这里有一种方法使用networkx

In [28]: import networkx as nx

创建

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

之间的距离节点 a, b, c其中链接 a, b和 'A，C' 一个grpah做

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

此外，你可以找到b and c

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

来源

2015-05-02 08:52:40 Zero

我试着它出来了，但在我使用的pScipter中没有包networkx。 python安装的版本是2.7，pyscripter的版本是2.53 ..它支持networkx吗？ –

pyscripter只是一个IDE。使用'pip install networkx'作为模块。 – Zero

之间使用dijkstra_path()

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

您也可以使用shortest_path()为路径的路径跟踪你可以找到所有与函数的路径，然后选择具有最小长度路径。

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

您可以使用返回的路径发电机following function：

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]))

，并找到与min功能与len为核心最小路径：

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

来源

2015-05-02 08:53:11 Kasramvd

您可以从该点使用BFS： http://en.wikipedia.org/wiki/Breadth-first_search

您也可以使用它运行为O（n^3）弗洛伊德 - Warshall算法，如果时间不是问题，你想简单：http://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm

来源

2015-05-02 08:57:35 Riko

Dijkstra算法解决“发现两个顶点之间的路径问题（或节点），使其构成边的权重之和最小化“。

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

所以，我认为，你可以用Dijkstra算法解决这个问题，其中从顶点到其相邻顶点的距离等于两个顶点之间的每一条路径。

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

的[最好的最短路径算法]

来源

2015-05-02 09:03:28 Eduen

您可以在这里添加解决方案的一些部分，而不仅仅是一个链接？ – abarisone

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

回答

相关问题