Поиск кратчайшего пути от начального узла к узлам друг друга с помощью метода Дейкстры - PullRequest
Новая
       105

Поиск кратчайшего пути от начального узла к узлам друг друга с помощью метода Дейкстры

5 голосов
/ 13 июля 2020

Это проблема hackerrank . Я делал некоторые основные проблемы с графиком c. Это неориентированный граф с равными весами на всех ребрах. Мне нужно распечатать вес, чтобы добраться до каждого узла из начального узла. Если он не может добраться, мне нужно вернуть -1. Я не должен включать стоимость исходного узла в список ответов

Это мое решение 

def bfs(n, m, edges, s):
    adjList = defaultdict(list)

    for u , v in edges:
        adjList[u].append((v , 6))
        adjList[v].append((u , 6))

    queue = []
    heapq.heappush(queue , (0,0,s))
    visited = set()
    visited.add(s)
    result = [-1] + [-1 for i in range(n)]

    while queue:
        costSoFar , travelled , nextNode = heapq.heappop(queue)
        result[nextNode] = costSoFar

        if travelled == m:
            break

        for neighbourNode , neighbourCost in adjList[nextNode]:
            if neighbourNode not in visited:
                heapq.heappush(queue , (costSoFar + 6 , travelled + 1 , neighbourNode))
                visited.add(neighbourNode) 
                   
    answer = result[ : s - 1] + result[s + 1 :]
    return answer

Я знаю, что Dijkstra здесь немного перебор, и мы можем решите это с помощью простого BFS. Но я хотел практиковать это. Это причина, по которой я пытался реализовать Dijkstra.

Проблема в том, что я могу передать примеры случаев , но это дает мне TLE и WA для других случаев. Может ли кто-нибудь сказать, где в этом я ошибаюсь, и исправить код той же реализацией.

...