Algorytm Dijkstry w Python & C++ (Przykład)

Jaka jest najkrótsza ścieżka lub najkrótsza odległość?

Ścieżka od wierzchołka źródłowego do wierzchołka docelowego, której koszt jest minimalny, to najkrótsza ścieżka lub najkrótsza odległość. W teorii grafów możliwe jest istnienie wielu tras od wierzchołka źródłowego do docelowego. Jeśli wśród tych tras istnieje trasa o minimalnym koszcie, nazywamy ją najkrótszą.

W tym przypadku „koszt” oznacza liczbę węzłów na trasie lub sumę kosztów na każdej krawędzi. Ścieżka może mieć jedną lub wiele krawędzi. Połączenie między dwoma wierzchołkami nazywane jest „krawędzią”. Istnieją różne rodzaje algorytmów najkrótszej ścieżki, takie jak algorytm Dijkstry i algorytm Bellmana-Forda.

Tutaj omówimy algorytm Dijkstry. Przyjrzyjmy się poniższemu grafowi ważonemu:

Wykres nieukierunkowany ważony

• Termin „ważony” oznacza koszt przejścia z jednego węzła do drugiego. Na przykład, przy przejściu z węzła 1 do węzła 2, koszt lub waga wynosi 1.
• Ścieżka pomiędzy węzłem 1 i węzłem 2 nazywana jest krawędzią.
• „Niekierowany” oznacza, że ​​można przemieszczać się z jednego węzła do drugiego i z powrotem do poprzedniego. Zatem, jeśli spróbujemy znaleźć wszystkie trasy z węzła 1 do węzła 7, będą one następujące:

Spośród tych czterech tras możemy zauważyć, że pierwsza kosztuje 7. Jest to zatem najkrótsza trasa pod względem kosztów.

Najkrótsza droga

Jak działa algorytm Dijkstry

Algorytm Dijkstry potrafi znaleźć najkrótszą odległość zarówno w grafach ważonych, jak i nieskierowanych. Algorytm ten jest zachłanny, ponieważ zawsze wybiera najkrótszy lub najbliższy węzeł od początku układu współrzędnych. Termin „zachłanny” oznacza, że ​​spośród zbioru wyników algorytm wybierze najlepszy z nich.

Tutaj staramy się znaleźć najkrótsze ścieżki spośród wszystkich innych tras. Zatem algorytm Dijkstry znajduje wszystkie najkrótsze ścieżki z jednego węzła źródłowego. W rezultacie zachowuje się jak… chciwy algorytm.

W sekcji „przykład” poniżej zobaczysz podejście krok po kroku. Działa ono w następujący sposób:

Krok 1) Zainicjuj węzeł początkowy kosztem 0, a resztę węzłów kosztem nieskończonym.
Krok 2) Utrzymuj tablicę lub listę, aby zachować track odwiedzonych węzłów.
Krok 3) Zaktualizuj koszt węzła do kosztu minimalnego. Można to zrobić, porównując bieżący koszt z kosztem ścieżki (jak pokazano w sekcji przykładowej).
Krok 4) Kontynuuj krok 3, aż odwiedzisz wszystkie węzły.

Po wykonaniu wszystkich tych kroków znajdziemy ścieżkę, która kosztuje minimum od źródła do miejsca docelowego.

Różnica między Dijkstrą a BFS, DFS

Główną różnicą między algorytmem Dijkstry a algorytmem BFS-DFS jest to, że Dijkstra jest algorytmem znajdowania najkrótszej ścieżki, podczas gdy BFS i DFS to ogólne algorytmy znajdowania ścieżki. W ogólnych przypadkach algorytmy BFS i DFS nie uwzględniają kosztu krawędzi podczas znajdowania ścieżki. Zatem algorytmy te nie gwarantują znalezienia najkrótszej ścieżki.

Demonstracja działania BFS na siatce 2D

Algoszkic, pokazując demonstrację BFS

Ta demonstracja wskazuje, że BFS znajduje tylko ścieżkę. Nie przejmuje się jednak wagą ścieżki. BFS (Przeszukiwanie wszerz) zakłada, że ​​podróż z jednego węzła do drugiego będzie kosztować tylko 1.

Spójrzmy na przykładowy wykres:

Tutaj BFS znajduje ścieżkę na poziomie 2. BFS przemierza graf w kolejności poziomów. Przemieszcza się więc w następujący sposób:

Krok 1) Rozpocznij od węzła „1” i odwiedź wszystkie sąsiednie węzły 2, 3, 4.

Krok 2) Oznacz węzły 2, 3 i 4 jako poziom 1 i odwiedź sąsiednie węzły. Będzie on kontynuował eksplorację wszystkich sąsiednich węzłów, aż dotrze do węzła docelowego.

Z punktu widzenia DFS ścieżka od 1 do 7 będzie przebiegać w następujący sposób:

• 1 → 2 → 3 → 7 (Oryginalny koszt 10, koszt DFS 3)
• 1 → 2 → 6 → 7 (Oryginalny koszt 7, koszt DFS 3)
• 1 → 3 → 7 (Oryginalny koszt 8, koszt DFS 2)
• 1 → 4 → 5 → 7 (Oryginalny koszt 13, koszt DFS 3)

Jak widać, DFS oblicza koszt ścieżki na podstawie liczby krawędzi. DFS wykonuje następujące czynności:

• DFS może znaleźć ścieżkę od źródła (wierzchołek początkowy) do miejsca docelowego.
• Nie może zagwarantować, czy odkryta ścieżka od węzła źródłowego do docelowego jest najkrótszą ścieżką, czy nie.

Jednak zgodnie z algorytmem Dijkstry, wybiera on krawędzie na podstawie ich kosztu. Jako algorytm zachłanny, wybiera ścieżki o minimalnym koszcie.

Przykład algorytmu Dijkstry

Algorytm Dijkstry wykorzystuje koszt lub wagę do obliczenia całkowitego kosztu ścieżki.

Celem algorytmu Dijkstry jest zminimalizowanie całkowitego kosztu lub wagi. W powyższym przykładzie znajdujemy najlepsze ścieżki od węzła 1 do węzła 7, a następnie obliczamy wszystkie koszty.

W algorytmie Dijkstry najkrótsze ścieżki są znajdowane poprzez obliczanie wag. Nie przeszukuje on wszystkich możliwych ścieżek. Zademonstrujmy algorytm Dijkstry na przykładzie. Załóżmy, że poproszono Cię o znalezienie najkrótszej ścieżki od węzła 1 do 7.

Poniżej przedstawiono kroki tego procesu:

Krok 1) Zainicjuj początkowy koszt węzła na 0. Przypisz „Inf” do pozostałych węzłów. Oznacza to, że nie istnieje ścieżka między źródłem a węzłem lub ścieżka ta nie została jeszcze odwiedzona.

Krok 2) Po wybraniu węzła 1 zostanie on oznaczony jako odwiedzony. Następnie zaktualizuj wszystkich sąsiadujących węzłów węzła 1. Węzły 2, 3, 4 to węzły sąsiadujące z węzłem 1.

Aktualizując koszt, musimy postępować zgodnie z poniższą procedurą:

Możemy zaktualizować koszt każdego węzła, korzystając z powyższego wzoru. Na przykład, byliśmy w węźle 1 i musieliśmy zaktualizować koszt sąsiednich węzłów 2, 3, 4. Po aktualizacji koszty będą wyglądać następująco:

Krok 3) Dla węzła „2” sąsiedzi to 6 i 3. Aktualizujemy koszt dla węzła „6”, porównując nieskończoność (wartość bieżącą) z kosztem węzła 2 + koszt ścieżki od 2 do 6. Mówiąc prościej, węzeł „6” będzie miał koszt 1 + 3 lub 4.

Węzeł 3 jest sąsiadem węzła 2. Jednak w poprzednim kroku obliczyliśmy jego koszt, który wynosił 7. Teraz, jeśli nasza ścieżka to 1-2-3, węzeł 3 będzie miał koszt 10. Ścieżka 1-2- 3 będzie kosztować 10, a 1 do 3 będzie kosztować 7.

Krok 4) Dla węzła 3, sąsiedni węzeł ma wartość 7. Porównując zatem bieżącą wartość węzła 7 z kosztem ścieżki (7+1) lub 8, zaktualizujemy koszt węzła 7. To jest 8. Znajdujemy więc ścieżkę od węzła 1 do węzła 7, która ma postać 1→3→7. Koszt wynosi 8.

Krok 5) Dla węzła 4 odpowiednio zaktualizujemy koszt węzła sąsiedniego. Węzeł „5” będzie miał zaktualizowany koszt 8. Po krokach 4 i 5 będzie wyglądać następująco:

Teraz ścieżka 1-3-7 ma koszt 8 (poprzednio). Węzeł „7” nie został oznaczony jako odwiedzony, ponieważ możemy dotrzeć do węzła „7” z węzła „6”. Ścieżka „1-2-6” miała koszt 4. Zatem ścieżka 1-2-6-7 będzie miała koszt 7.

Ponieważ 7 < 8, najkrótsza ścieżka od wierzchołka źródłowego „1” do wierzchołka docelowego „7” będzie wynosić 1-2-6-7, a koszt wyniesie 7. Wcześniej było to 1-3-7, a koszt wyniósł 8. Ostateczny graf będzie więc wyglądał następująco:

Krawędź oznaczona czarną linią to nasza najkrótsza droga od 1 do 7 i będzie nas to kosztować 7.

Rzekomy Code Algorytm Dijkstry

Oto pseudokod algorytmu Dijkstry:

Dijkstra(G, S):
  for each vertex V in G
    distance[V] <- Infinity
    previous[V] <- NULL
    if V does not equal S, then,
      (priority queue) Q.push(V)
  distance[S] = 0
  While Q is not empty
    U <- Extract the MIN from Q
    For each unvisited adjacent V of U
      TotalDistance <- distance[U] + edge_cost(U, V)
      if TotalDistance is less than distance[V], then
        distance[V] <- TotalDistance
        previous[V] <- U
  return distance, previous

C++ Implementacja algorytmu Dijkstry

Aby zaimplementować algorytm Dijkstry za pomocą C++Oto kod:

#include <bits/stdc++.h>
using namespace std;
#define size 7
int minimumDistance(int distance[], bool visited[]) {
  int min = INT_MAX;
  int min_index = INT_MAX;
  for (int i = 0; i < size; i++) {
    if (!visited[i] && distance[i] <= min) {
      min = distance[i];
      min_index = i;
    }
  }
  return min_index;
}
void printParentPath(int parent[], int i) {
  if (parent[i] == -1) {
    return;
  }
  printParentPath(parent, parent[i]);
  cout << i + 1 << " ";
}
void dijkstra(int graph[size][size], int source) {
  int distance[size];
  bool visited[size];
  int parent[size];
  for (int i = 0; i < size; i++) {
    parent[0] = -1;
    distance[i] = INT_MAX;
    visited[i] = false;
  }
  distance[source] = 0;
  for (int i = 0; i < size - 1; i++) {
    int U = minimumDistance(distance, visited);
    visited[U] = true;
    for (int j = 0; j < size; j++) {
      int curr_distance = distance[U] + graph[U][j];
      if (!visited[j] && graph[U][j] &&
          curr_distance < distance[j]) {
        parent[j] = U;
        distance[j] = curr_distance;
      }
    }
  }
  cout << "Vertex\t\tDistance\tPath" << endl;
  for (int i = 1; i < size; i++) {
    cout << source + 1 << "->" << i + 1 << "\t\t" << distance[i] << "\t\t"
         << source + 1 << " ";
    printParentPath(parent, i);
    cout << endl;
  }
}
int main() {
  int graph[size][size] = {{0, 1, 7, 6, 0, 0, 0}, {1, 0, 9, 0, 0, 3, 0},
                           {7, 9, 0, 0, 0, 0, 1}, {6, 0, 0, 0, 2, 0, 0},
                           {0, 0, 0, 2, 0, 0, 0}, {0, 3, 0, 0, 0, 0, 3},
                           {0, 0, 0, 0, 5, 3, 0}};
  dijkstra(graph, 0);
}

Wyjście:

Vertex     Distance        Path

1->2           1             1 2
1->3           7             1 3
1->4           6             1 4
1->5           8             1 4 5
1->6           4             1 2 6
1->7           7             1 2 6 7

Python Implementacja algorytmu Dijkstry

Aby zaimplementować algorytm Dijkstry za pomocą PythonOto kod:

num_of_vertex = 7
def minimumDistance(distance, visited):
    _min = 1e11
    min_index = 1e11
    for i in range(num_of_vertex):
        if not visited[i] and distance[i] <= _min:
            _min = distance[i]
            min_index = i
    return min_index

def printParentNode(parent, i):
    if parent[i] == -1:
        return
    printParentNode(parent, parent[i])
    print("{} ".format(i + 1), end="")

def dijkstra(graph, src):
    distance = list()
    visited = list()
    parent = list()
    for i in range(num_of_vertex):
        parent.append(-1)
        distance.append(1e11)
        visited.append(False)
    distance[src] = 0
    for i in range(num_of_vertex - 1):
        U = minimumDistance(distance, visited)
        visited[U] = True
        for j in range(num_of_vertex):
            curr_distance = distance[U] + graph[U][j]
            if not visited[j] and graph[U][j] and curr_distance < distance[j]:
                parent[j] = U
                distance[j] = curr_distance
    print("Vertex\t\tDistance\tPath")
    for i in range(num_of_vertex):
        print("{}->{}\t\t{}\t\t{} ".format(src + 1, i + 1, distance[i], src + 1), end="")
        printParentNode(parent, i)
        print("")

graph = [
    [0, 1, 7, 6, 0, 0, 0],
    [1, 0, 9, 0, 0, 3, 0],
    [7, 9, 0, 0, 0, 0, 1],
    [6, 0, 0, 0, 2, 0, 0],
    [0, 0, 0, 2, 0, 0, 0],
    [0, 3, 0, 0, 0, 0, 3],
    [0, 0, 0, 0, 5, 3, 0]
]
dijkstra(graph, 0)

Wyjście:

Vertex     Distance        Path

1->1           0              1
1->2           1              1 2
1->3           7              1 3
1->4           6              1 4
1->5           8              1 4 5
1->6           4              1 2 6
1->7           7              1 2 6 7

Możemy zobaczyć, że algorytm oblicza najkrótszą odległość od węzła źródłowego.

Zastosowanie algorytmu Dijkstry

Algorytm Dijkstry ma szeroki wachlarz zastosowań. Jest on między innymi szeroko stosowany w dziedzinie sieci komputerowych. Oto kilka praktycznych zastosowań algorytmu Dijkstry:

Dijkstra w Google Mapy: Jak widać we fragmencie kodu zamieszczonym powyżej, algorytm ten stanowi podstawę znajdowania najkrótszych ścieżek.

Google Nie korzysta z prostego algorytmu Dijkstry. Zamiast tego używa zmodyfikowanej wersji. Po wybraniu celu podróży wyświetla wiele ścieżek. Google Mapy. Spośród tych ścieżek, niektóre są sortowane dla użytkownika. Ścieżki te są wybierane na podstawie „czasu”. Zatem „czas” jest kosztem krawędzi dla najkrótszej ścieżki.

Dijkstra w routingu IP: Routing IP to terminologia sieciowa. Opisuje sposób, w jaki pakiet danych jest przesyłany do odbiorcy różnymi ścieżkami. Ścieżki te obejmują routery, serwery i inny sprzęt. W routingu IP występują różne typy protokołów.

Protokoły te pomagają routerowi znaleźć najkrótsze ścieżki do przesyłania danych. Jedną z nazw protokołów jest „OSPF (Open Shortest Path First)”. OSPF wykorzystuje algorytm Dijkstry. Router utrzymuje tablicę tras. Każdy router udostępnia swoją tablicę sąsiednim routerom. Po otrzymaniu zaktualizowanej tablicy muszą one ponownie obliczyć wszystkie ścieżki. W tym momencie router korzysta z algorytmu Dijkstry.

Ograniczenia algorytmu Dijkstry

Algorytm Dijkstry nie gwarantuje najkrótszej ścieżki w grafie z ujemnymi krawędziami. Algorytm Dijkstry opiera się na następujących zasadach:

• Z jednego węzła do drugiego zostanie poprowadzona jedna najkrótsza ścieżka.
• Po wybraniu najkrótszej ścieżki pomiędzy dwoma węzłami nie będzie ona obliczana ponownie.

Tutaj zwróć uwagę na dwa przykłady z ujemnymi krawędziami.

Na lewym wykresie, Graf ma trzy wierzchołki. Dijkstra będzie działał na nim w następujący sposób:

Krok 1) Początkowy wierzchołek „1” zostanie zainicjowany na zero. Pozostałe węzły będą miały nieskończoność.

Krok 2) Oznacz węzeł „1” jako odwiedzony i uwzględnij go w najkrótszej ścieżce.

Krok 3) Odległość między węzłem źródłowym 1 a węzłami „2” i „3” jest równa nieskończoności, ponieważ najkrótsza ścieżka nie została jeszcze obliczona. Zatem każda ścieżka, której koszt jest mniejszy niż nieskończoność, zostanie dodana do najkrótszej ścieżki (podejście zachłanne).

Krok 4) Aktualizuję odległość od wierzchołka źródłowego „1” do „2”. Aktualna waga będzie wynosić 5 (5 < nieskończoność). Analogicznie, zaktualizuj odległość od węzła „1” do „3” z wagą równą 3.

Krok 5) Jeśli teraz sprawdzimy najkrótsze odległości od węzła „1”, okaże się, że 5 to najkrótsza odległość dla krawędzi 1→2. Zatem węzeł „2” zostanie oznaczony jako odwiedzony. Podobnie węzeł „3” również zostanie oznaczony jako odwiedzony, ponieważ najkrótsza odległość wynosi 3.

Jeśli jednak przyjrzymy się bliżej, istnieje ścieżka 1-3-2, która będzie kosztować tylko 2. Dijkstra pokazuje jednak, że od węzła „1” do węzła „2” najkrótsza odległość wynosi 5. Zatem Dijkstra nie obliczył poprawnie najkrótszej odległości. Powodem jest to, że Dijkstra jest algorytmem zachłannym. Oznacza to, że po oznaczeniu węzła jako odwiedzonego, nie zostanie on ponownie rozpatrzony, chociaż może istnieć krótsza ścieżka. Ten problem występuje tylko wtedy, gdy krawędzie mają ujemny koszt lub ujemną wagę.

W tym scenariuszu Dijkstra nie potrafi obliczyć najkrótszej ścieżki między dwoma węzłami. W rezultacie algorytm ten ma pewne wady. Aby rozwiązać ten problem z ujemnymi krawędziami, zastosowano inny algorytm o nazwie „Algorytm Bellmana-Forda”. Algorytm ten może działać z ujemnymi krawędziami.

Złożoność algorytmu Dijkstry

Powyższa implementacja używała dwóch pętli „for”. Pętle te działają dla liczby wierzchołków. Zatem złożoność czasowa wynosi O(V²). W tym przypadku termin „O” jest oznaczeniem dającym założenie dla algorytmu Dijkstry.

Graf możemy zapisać za pomocą „kolejki priorytetowej”. Kolejka priorytetowa to binarna struktura danych w formie sterty. Będzie ona bardziej wydajna niż macierz 2D. Krawędź o minimalnym koszcie będzie miała wysoki priorytet. Wtedy złożoność czasowa będzie… O(E log V). Tutaj E jest liczbą krawędzi, a V jest liczbą wierzchołków.

Złożoność kosmiczna to O(V²), ponieważ używamy macierzy sąsiedztwa (Tablica 2D). Złożoność przestrzeni można zoptymalizować, używając listy sąsiedztwa lub struktury danych kolejki.

FAQ