Where should I modify my breadth first search algo for finding the shortest path between 2 nodes?

Question

I am taking a graph algo course, i am stuck with this problem of finding the shortest path between 2 vertices.

The problem statement : Given an un-directed graph with n vertices and m edges and two vertices u and v, compute the length of the shortest path between u and v. Output the minimum number of edges in a path from u to v, or −1 if there is no path.

My code is passing some test-cases, but few of them are failing, and i can't really see where am i going wrong, so any kind of insight would really be helpful.

def explore(arr, start, end, vis):

    vis[start] = 0; q = [start] # queue for storing the node for exploring

    while len(q) != 0:  # iterates till queue isn't empty
        u = q.pop()
        for i in arr[u]: # checks for all nodes connected to uth node
            if vis[i] == -1: # if the node is unvisited
                q.insert(0, i)
                vis[i] = vis[u] + 1
            elif vis[i] > vis[u] + 1: # if the visited node has shorter path
                q.insert(0, i)
                vis[i] = vis[u] + 1

    return vis[end]

if True:
    n, m = map(int, input().split()) # n : vertices, m : edges
    arr = {} # stores edges

    for i in range(m): # accepts edges as inputs
        a, b = map(int, input().split()) # (a,b) >(0,0)

        if a-1 in arr.keys():
            arr[a-1].append(b-1)
        else:
            arr[a-1] = [b-1]

        if b-1 in arr.keys():
            arr[b-1].append(a-1)
        else:
            arr[b-1] = [a-1]

    if m > 0:
        start, end = map(int, input().split()) # start : source node, end = dest node 
        vis = [-1 for i in range(n)] # will store shortest path for each node
        print(explore(arr, start-1, end-1, vis))
    else:
        print(-1)

Answer 1

You have issues with your code due to problems with indexes. You use indexes started from 1 here: q = [start] but later you use indexes started from 0: for i in arr[u] (note, no -1) and so on. I strictly recommend to use indexing from 0 everywhere - it's definitely more readable and helps to avoid possible errors with indexes. Also, you don't really need your elif case if you add new item to the end of q (you insert it to start of q for some reason). Corrected code (warning - indexes in input parameters starts from 0 everywhere!):

def explore(arr, start, end, vis):
    vis[start] = 0
    q = [start] # queue for storing the node for exploring

    while len(q): # iterates till queue isn't empty
        u = q.pop()
        for i in arr[u]: # checks for all nodes connected to uth node
            if vis[i] == -1: # if the node is unvisited
                q.append(i)
                vis[i] = vis[u] + 1

    return vis[end]