# 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.

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

Here's one way to do using networkx

``````In : import networkx as nx
``````

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

``````In : g = nx.Graph()

In : g.add_edge('a', 'b')

In : g.add_edge('a', 'c')
``````

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

``````In : nx.dijkstra_path_length(g, 'b', 'c')
Out: 2
``````

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

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

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

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

``````In : import networkx as nx
``````

``````In : g = nx.Graph()

In : g.add_edge('a', 'b')

In : g.add_edge('a', 'c')
``````

``````In : nx.dijkstra_path_length(g, 'b', 'c')
Out: 2
``````

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

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

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

``````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_path = min(all_paths(graph, start, goal),key=len)
``````

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

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 %

python  algorithm  graph  shortest-path