Przeszukiwanie wszerz i algorytm Dijkstry

Graf to zbiór wierzchołków (miast, skrzyżowań, osób) i krawędzi między nimi. Dwa podstawowe algorytmy z zakresu rozszerzonego szukają w grafie dróg: przeszukiwanie wszerz (BFS) liczy najmniejszą liczbę krawędzi do każdego wierzchołka, a algorytm Dijkstry najkrótszą drogę, gdy krawędzie mają długości.

Każdy przykład przejdziesz krok po kroku w kursie Algorytmy: zakres rozszerzony: w przeglądarce, bez instalowania niczego i bez konta. Podgląd zmiennych pokazuje kolejkę i tablicę odległości po każdym kroku.

Przejdź przeszukiwanie wszerz krok po kroku

Przeszukiwanie wszerz i odległości

Graf zapisany jest listą sąsiedztwa (słownik: wierzchołek i lista sąsiadów). Kolejka trzyma wierzchołki do odwiedzenia w kolejności odległości od startu:

from collections import deque

graph = {1: [2, 3], 2: [1, 4], 3: [1], 4: [2, 5], 5: [4], 6: []}


def bfs(graph, start):
    distance = {start: 0}
    queue = deque([start])
    while queue:
        u = queue.popleft()
        for v in graph[u]:
            if v not in distance:
                distance[v] = distance[u] + 1
                queue.append(v)
    return distance


print(bfs(graph, 1))

{1: 0, 2: 1, 3: 1, 4: 2, 5: 3}

Wierzchołka 6 nie ma w wyniku: nie da się do niego dojść z 1. Uruchomienie BFS od każdego jeszcze nieodwiedzonego wierzchołka liczy składowe spójności.

Najkrótsze drogi algorytmem Dijkstry

Krawędzie mają teraz długości. Algorytm za każdym razem bierze wierzchołek o najmniejszej znanej odległości (z kolejki priorytetowej heapq), zatwierdza ją i poprawia odległości sąsiadów:

import heapq

roads = {
    "A": [("B", 4), ("C", 1)],
    "B": [("A", 4), ("C", 2), ("D", 1)],
    "C": [("A", 1), ("B", 2), ("D", 5)],
    "D": [("B", 1), ("C", 5)],
}


def dijkstra(graph, start):
    distance = {start: 0}
    heap = [(0, start)]
    while heap:
        d, u = heapq.heappop(heap)
        if d > distance[u]:
            continue
        for v, w in graph[u]:
            if v not in distance or d + w < distance[v]:
                distance[v] = d + w
                heapq.heappush(heap, (d + w, v))
    return distance


print(dijkstra(roads, "A"))

{'A': 0, 'B': 3, 'C': 1, 'D': 4}

Droga z A do B przez C (1 + 2) jest krótsza niż bezpośrednia (4). Pseudokod niżej zamiast kolejki priorytetowej szuka najbliższego wierzchołka pętlą po macierzy wag: wolniej dla dużych grafów, ale prościej do zapisania na maturze.

Lista kroków, pseudokod i schemat blokowy

Podstawa programowa wymaga, żeby uczeń opisywał problem specyfikacją (dane i wynik) i zapisywał algorytm listą kroków albo pseudokodem, a w szkole rysuje się też schematy blokowe. Pseudokod jest w stylu arkuszy maturalnych: ← to przypisanie, div i mod to iloraz i reszta z dzielenia całkowitego, a elementy tablic i znaki napisów są numerowane od 1 (w Pythonie od 0). Te same zapisy są w kursie przy lekcjach tematu, pod przyciskiem Algorytm.

Przeszukiwanie grafu wszerz (BFS) i odległości

Specyfikacja. Dane: graf o n wierzchołkach jako macierz sąsiedztwa A[1..n][1..n] (1 = krawędź) i wierzchołek startowy s. Wynik: D[v]: najmniejsza liczba krawędzi z s do v (-1, gdy v jest nieosiągalny).

Lista kroków:

1. Wczytaj n, macierz A i wierzchołek s. Ustaw D[v] = -1 dla każdego v (nieodwiedzony), D[s] = 0.
2. Wstaw s do kolejki Q (p to początek kolejki, k jej koniec).
3. Jeśli kolejka jest pusta (p > k), przejdź do kroku 5.
4. Zdejmij z początku kolejki wierzchołek u. Każdego nieodwiedzonego sąsiada v wierzchołka u oznacz odległością D[v] = D[u] + 1 i wstaw na koniec kolejki. Wróć do kroku 3.
5. Wypisz D.

Pseudokod:

wczytaj n, A, s
dla v = 1, 2, ..., n wykonuj
  D[v] ← -1
D[s] ← 0
Q[1] ← s
p ← 1
k ← 1
dopóki p ≤ k wykonuj
  u ← Q[p]
  p ← p + 1
  dla v = 1, 2, ..., n wykonuj
    jeżeli A[u][v] = 1 i D[v] = -1 to
      D[v] ← D[u] + 1
      k ← k + 1
      Q[k] ← v
wypisz D

Schemat blokowy:

Najkrótsze drogi algorytmem Dijkstry

Specyfikacja. Dane: graf o n wierzchołkach z dodatnimi wagami krawędzi W[1..n][1..n] (0 = brak krawędzi) i wierzchołek startowy s. Wynik: D[v]: długość najkrótszej drogi z s do v (1000000, gdy v jest nieosiągalny).

Lista kroków:

1. Wczytaj n, macierz wag W i wierzchołek s. Ustaw D[v] = 1000000 i V[v] = fałsz (v nie jest jeszcze gotowy) dla każdego v, D[s] = 0.
2. Powtórz n razy kroki 3-4.
3. Wybierz wierzchołek u, który nie jest gotowy i ma najmniejsze D[u]. Oznacz go jako gotowy: jego odległość już się nie zmieni.
4. Dla każdego sąsiada v wierzchołka u: jeśli D[u] + W[u][v] < D[v], zastąp D[v] liczbą D[u] + W[u][v] (droga przez u jest krótsza).
5. Wypisz D.

Pseudokod:

wczytaj n, W, s
dla v = 1, 2, ..., n wykonuj
  D[v] ← 1000000
  V[v] ← fałsz
D[s] ← 0
dla k = 1, 2, ..., n wykonuj
  u ← 0
  dla v = 1, 2, ..., n wykonuj
    jeżeli nie V[v] i (u = 0 lub D[v] < D[u]) to
      u ← v
  V[u] ← prawda
  dla v = 1, 2, ..., n wykonuj
    jeżeli W[u][v] > 0 i D[u] + W[u][v] < D[v] to
      D[v] ← D[u] + W[u][v]
wypisz D

Schemat blokowy:

Najczęstsze błędy

• Oznaczanie odwiedzin przy zdejmowaniu z kolejki. W BFS wierzchołek trzeba oznaczyć przy wstawianiu do kolejki, inaczej trafi tam kilka razy.
• Graf nieskierowany zapisany w jedną stronę. Krawędź A-B musi być na liście sąsiadów A i na liście sąsiadów B.
• Ujemne wagi w algorytmie Dijkstry. Zatwierdzona odległość może się wtedy jeszcze zmniejszyć i wynik jest błędny.
• Kolejka na liście z pop(0). Działa, ale wolno. Użyj collections.deque.

Ćwicz w przeglądarce

W temacie o grafach kursu Algorytmy: zakres rozszerzony:

• graf jako lista sąsiedztwa,
• najmniej przesiadek między miastami,
• najkrótsza droga w grafie z wagami,
• liczba składowych spójności.

Przycisk Algorytm przy tych lekcjach pokazuje listę kroków, pseudokod i schemat blokowy. Pełna lista: algorytmy.

Dla nauczycieli

Grafy warto najpierw narysować na tablicy, a potem porównać kolejne stany kolejki i tablicy odległości z podglądem zmiennych podczas krokowania. W BitWizards przydzielasz kurs klasie i widzisz przebieg pisania kodu każdego ucznia. Platforma jest darmowa dla szkół - jak zacząć.