How to do shortest path algorithm for unweighted graph?

2018-06-12 08:09:01

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??

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

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)

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://www.djcxy.com/p/35304.html

上一篇: SOAP响应/请求，然后如何将其转换为PHP

下一篇: 如何为未加权图做最短路径算法？