Breadth First Search on an unweighted bidirectional graph

Question

I have been trying to use BFS to find the shortest path between 2 nodes. I have tried looking at tutorials and online readings but none of them were clear enough for me. I can only traverse through the graph currently, but I am not really sure on what checks do I need to have to find the minimum path between 2 nodes in a graph. The graph is unweighted and bidirectional. This is my code to traverse through all the nodes in the graph using BFS.

def bredthfirstsearch(start, end, graph):
    queue = [start]
    visited = [False]*(roads+1) #marks if a node has been visited
    visited[start] = True
    while len(queue) != 0:
        # source node popped and later used to find neighboring nodes
        node = queue.pop(0)

        for item in graph[node]:
            # if the node has not been found previously
            if visited[item[0]] == False:
                queue.append(item[0]) # it is added to the queue for future checking on its neighbors 
                visited[item[0]] = True #node then set to true

Now I may need an additional array to store the shortest path but I am not sure how to do that. Thank you so much.

Daniel Shterenberg Daniel Shterenberg · Accepted Answer · 2018-10-13T15:43:36

BFS will help you find all shortest paths from a specific node. If you want use BFS to find the minimal path between every pair of nodes in the graph you will need to run BFS from almost every node (almost every node because you will have some leaves calculated already).

Here is how to find the distance between two nodes. Using BFS on vertex a (arbitrary vertex) you will be able to find all shortest paths (distances) to the other vertices. To calculate the distance you will want to have a "level counter". Here is a pseudo-code that will help you do so:

q = new Queue()
dist_array = new Array(N) //and Set each value to infinity
distance=0
q.enqueue(a) //a is the selected node
dist_array[a] = 0
while q not empty:
    v = q.dequeue()
    ++distance
    for each neighbor x of v:
        if distance_array[x] < infinity:
             continue
        d[x] = distance
        q.enqueue(x)

lets say that your graph is G=(V,E) when:

V = {a,b,c,d,e,f}, |V| = N = 6
E = {(a,b), (a,c), (a,e), (b,d), (b,e), (d,f)}, |E| = M = 6

If we will run this code on our graph, we will get the following result

dist=1: a->b, a->c, a->e
dist=2: a->d
dist=3: a->f

Breadth First Search on an unweighted bidirectional graph

1 Answers