找到你要的答案

Q:How to do shortest path algorithm for unweighted graph?

Q:如何做的最短路径算法的加权图?

I'm trying to find the shortest path from a vertex to another of a connected, unweighted graph.

In this problem,the distance from a vertex to its adjacent vertex will be equal to 1.ie., if a graph with edges (a,b),(a,c) is considered, the distance from a to b and c will be 1 and the distance from b to c will be 2. Also, an adjacency list is maintained to store all the adjacent vertices of each vertex.

So, is there any algorithms to find all the shortest paths for the given problem??

我想从一个点到另一个连接找到最短路径,加权图。

In this problem,the distance from a vertex to its adjacent vertex will be equal to 1.ie., if a graph with edges (a,b),(a,c) is considered, the distance from a to b and c will be 1 and the distance from b to c will be 2. Also, an adjacency list is maintained to store all the adjacent vertices of each vertex.

那么,有没有算法找到所有的最短路径给定的问题??

answer1: 回答1:

You could use dijkstra's algorithm to find the distance.

Here's one way to do using networkx

In [28]: import networkx as nx

Create a grpah with nodes a, b, c where links are a, b and 'a, c'

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

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

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

Then using nx.dijkstra_path_length() find the distance between b and c

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

Also, you can find the path trail using dijkstra_path()

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

You could also use shortest_path() for path between b and c

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

你可以使用Dijkstra算法寻找距离。

这是做的一个方法使用NetworkX

In [28]: import networkx as nx

创建一个节点,B,C中的链接是一个合图,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']
answer2: 回答2:

You can find all the paths with a function then choose the path with minimum length.

But note that this problem is more based on your search algorithm, for example with a BFS algorithm :

You can use the following function that return a generator of paths :

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

And find the minimum path with min functions with len as its key :

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

您可以找到所有路径的功能,然后选择路径的最小长度。

但是请注意,这个问题更多的是基于您的搜索算法,例如用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_path = min(all_paths(graph, start, goal),key=len)
answer3: 回答3:

You can use BFS from that point: http://en.wikipedia.org/wiki/Breadth-first_search

You can also use Floyd–Warshall algorithm which runs O(n^3) if time is not an issue and you want simplicity: http://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm

你可以从这一点:http://en.wikipedia.org/wiki/breadth-first_search BFS

你也可以使用弗洛依德–Warshall算法是O(n ^ 3)如果时间不是问题,你想的简单:HTTP:/ /恩。维基百科。org /维基/弗洛依德% E2 % 80% 93warshall_algorithm

answer4: 回答4:

Dijkstra algorithm solve "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

So, i think that you can solve this with Dijkstra where the distance from a vertex to its adjacent vertex is equal for every path between two vertex.

Anyway, you can use BFS http://en.wikipedia.org/wiki/Breadth-first_search

Dijkstra算法解决“找两顶点之间的路径问题(或节点)在图中,其构成的边的权重的总和最小化”。

HTTP:/ /恩。维基百科。org /维基/ 27s_algorithm Dijkstra %

所以,我认为你可以解决这个Dijkstra,从一个顶点到其相邻顶点的距离是相等的两顶点之间的每一条路。

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

python  algorithm  graph  shortest-path