Najkrótsza droga w grafie z wagami

Grafy: przeszukiwanie i najkrótsze drogi - Algorytmy: zakres rozszerzony (Python)

Gdy krawędzie mają długości, liczba krawędzi nie wystarcza. **Algorytm Dijkstry** w każdym kroku wybiera nieodwiedzony wierzchołek o najmniejszej znanej odległości (metoda zachłanna) i poprawia odległości jego sąsiadów. Kolejka priorytetowa `heapq` szybko podaje wierzchołek o najmniejszej odległości.

import heapq

graph = {
    "A": [("B", 4), ("C", 1)],
    "B": [("A", 4), ("C", 2), ("D", 5)],
    "C": [("A", 1), ("B", 2), ("D", 8)],
    "D": [("B", 5), ("C", 8)],
}
distance = {"A": 0}
heap = [(0, "A")]
while heap:
    d, vertex = heapq.heappop(heap)
    if d > distance[vertex]:
        continue
    for neighbour, weight in graph[vertex]:
        new = d + weight
        if neighbour not in distance or new < distance[neighbour]:
            distance[neighbour] = new
            heapq.heappush(heap, (new, neighbour))
print(dict(sorted(distance.items())))

Ładowanie interaktywnego edytora... Jeśli się nie pojawi, włącz JavaScript.

Wszystkie lekcje kursu Algorytmy: zakres rozszerzony·Zaloguj się, aby zapisać postęp na koncie.