Mniej krawędzi to nie krócej

Najkrótsza droga w grafie z wagami: algorytm Dijkstry - Informatyka - liceum klasa 3, zakres rozszerzony (Python)

W grafie z wagami najkrótsza droga to najmniejsza **suma wag**, a nie najmniejsza liczba krawędzi. Z `A` do `B` bezpośrednio jest 4, a przez `C` tylko `1 + 2 = 3`. BFS znalazłby drogę z jedną krawędzią, czyli złą. Program porównuje obie trasy.

roads = [("A", "B", 4), ("A", "C", 1), ("C", "B", 2), ("B", "D", 5), ("C", "D", 8), ("D", "E", 3)]
graph = {}
for a, b, w in roads:
    graph.setdefault(a, []).append((b, w))
    graph.setdefault(b, []).append((a, w))
weight = {(a, b): w for a in graph for b, w in graph[a]}
print("A-B:", weight[("A", "B")])
print("A-C-B:", weight[("A", "C")] + weight[("C", "B")])

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

Wszystkie lekcje kursu Informatyka - liceum klasa 3, zakres rozszerzony·Zaloguj się, aby zapisać postęp na koncie.