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

Question

我正在学习图算法类(class)，我被这个寻找两个顶点之间的最短路径的问题所困扰。

问题陈述:给定一个有 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] 但稍后您使用从 0 开始的索引:for i in arr [u](注意，没有-1)等等。我强烈建议在任何地方都使用 0 的索引——它绝对更具可读性并且有助于避免索引可能出现的错误。此外，如果您将新项目添加到 q 的末尾(将其插入到 q 的开头)，您实际上并不需要 elif 案例因为某些原因)。更正后的代码(警告 - 输入参数中的索引无处不在从 0 开始!):

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]