Где я должен изменить свой алгоритм поиска в ширину, чтобы найти кратчайший путь между двумя узлами?

Question

Я беру курс по графику, я застрял с проблемой поиска кратчайшего пути между 2 вершинами .

Постановка задачи: Учитывая неориентированный граф с 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 везде - оно определенно более читабельно и помогает избежать возможных ошибок с индексами. Кроме того, вам не нужен ваш elif кейс, если вы добавляете новый элемент в конец q (вы по какой-то причине вставляете его в начало q). Исправленный код (предупреждение - индексы во входных параметрах начинаются с 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]