我应该在哪里修改广度优先搜索算法以找到2个节点之间的最短路径？

Question

我正在学习一个图算法课程，我一直陷入寻找两个顶点之间最短路径的问题。

问题陈述：给定一个具有n个顶点和m个边以及两个顶点u和v的无向图，计算u和v之间最短路径的长度。输出从u到v的路径中最小边数，或者如果没有路径，则为？1。

我的代码正在通过一些测试用例，但其中很少有失败，而且我真的看不到哪里出了问题，因此，任何形式的洞察都将真正有用。

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

由于索引问题，您的代码出现问题。您使用从此处开始的索引1：但稍后您使用从:q = [start]开始的索引（注意，不是）等等。我强烈建议在任何地方使用索引- 它绝对更具可读性，并且有助于避免索引可能出现的错误。另外，如果您将新项目添加到末尾（出于某种原因将其插入到开头） ，您实际上并不需要您的案例。更正的代码（警告 - 输入参数中的索引从各处开始！）：0for i in arr[u]-10elifqq0

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]