Dijkstrův algoritmus v Python & C++ (Příklad)

Jaká je nejkratší cesta nebo nejkratší vzdálenost?

Cesta ze zdrojového vrcholu do cílového vrcholu, která má minimální náklady, je nejkratší cesta nebo nejkratší vzdálenost. V teorii grafů je možné mít více cest ze zdroje do cíle. Pokud mezi těmito cestami existuje trasa s minimálními náklady, nazýváme ji nejkratší cestou.

Zde „náklady“ znamenají počet uzlů v trase nebo součet nákladů na každé hraně. Cesta může mít jednu nebo více hran. Spojení mezi dvěma vrcholy se nazývá „hrana“. Existují různé typy algoritmů pro nejkratší cestu, jako je Dijkstrův algoritmus a Bellman-Fordův algoritmus.

Zde si povíme o Dijkstrově algoritmu. Podívejme se na následující vážený graf:

Neorientovaný vážený graf

• Termín „vážený“ označuje náklady na přesun z jednoho uzlu do druhého. Například při přesunu z uzlu 1 do uzlu 2 jsou náklady nebo váha 1.
• Cesta mezi uzlem 1 a uzlem 2 se nazývá hrana.
• „Neorientované“ znamená, že se můžete přesunout z jednoho uzlu do druhého a zpět k předchozímu uzlu. Pokud se tedy pokusíme najít všechny trasy z uzlu 1 do uzlu 7, budou vypadat takto:

Z těchto čtyř tras vidíme, že první trasa stojí 7. Je to tedy z hlediska nákladů nejkratší cesta.

Nejkratší cesta

Jak funguje Dijkstrův algoritmus

Dijkstrův algoritmus dokáže najít nejkratší vzdálenost v orientovaných i neorientovaných vážených grafech. Tento algoritmus je chamtivý, protože vždy vybírá nejkratší nebo nejbližší uzel z počátku. Termín „chamtivý“ znamená, že z množiny výsledků nebo výsledků algoritmus vybere ten nejlepší.

Zde se snažíme najít nejkratší cesty mezi všemi ostatními cestami. Dijkstrův algoritmus tedy najde všechny nejkratší cesty z jednoho zdrojového uzlu. V důsledku toho se chová jako chamtivý algoritmus.

V níže uvedené části „příklad“ uvidíte postup krok za krokem. Funguje následovně:

Krok 1) Inicializujte počáteční uzel s 0 náklady a zbytek uzlů s nekonečnou cenou.
Krok 2) Udržovat pole nebo seznam pro uchování track navštívených uzlů.
Krok 3) Aktualizujte cenu uzlu o minimální cenu. To lze provést porovnáním aktuální ceny s cenou cesty (ukázáno v příkladové části).
Krok 4) Pokračujte krokem 3, dokud nenavštívíte všechny uzly.

Po dokončení všech těchto kroků najdeme cestu, která stojí minimum od zdroje k cíli.

Rozdíl mezi Dijkstrou a BFS, DFS

Hlavní rozdíl mezi Dijkstrou a BFS-DFS spočívá v tom, že Dijkstra je algoritmus pro hledání nejkratší cesty, zatímco BFS a DFS jsou obecné algoritmy pro hledání cesty. V obecných případech BFS a DFS při hledání cesty nezohledňují cenu hran. Tyto algoritmy tedy nemohou zaručit nalezení nejkratší cesty.

2D mřížková ukázka fungování BFS

Algosketch, ukazující ukázku BFS

Tato ukázka ukazuje, že BFS najde pouze cestu. Nezáleží však na hmotnosti cesty. BFS (První vyhledávání podle šířky) předpokládá, že cestování z jednoho uzlu do druhého bude stát pouze 1.

Podívejme se na příklad grafu:

Zde BFS najde cestu na úrovni 2. BFS prochází grafem v pořadí po úrovních. Takže se pohybuje takto:

Krok 1) Začněte od uzlu „1“ a navštivte všechny sousední uzly 2, 3, 4.

Krok 2) Označí uzly 2, 3, 4 jako uzly úrovně 1 a navštíví jejich sousední uzly. Bude pokračovat v prozkoumávání všech sousedních uzlů, dokud nedosáhne cílového uzlu.

Pokud jde o DFS, bude procházet cestou od 1 do 7 takto:

• 1→2→3→7 (původní cena 10, cena DFS 3)
• 1→2→6→7 (původní cena 7, cena DFS 3)
• 1→3→7 (původní cena 8, cena DFS 2)
• 1→4→5→7 (původní cena 13, cena DFS 3)

Jak vidíme, DFS vypočítává cenu cesty s počtem hran. DFS provádí následující:

• DFS může najít cestu ze zdroje (počáteční vrchol) do cíle.
• Nemůže zaručit, zda zjištěná cesta ze zdrojového uzlu do cíle je nejkratší cestou nebo ne.

Nicméně, z hlediska Dijkstrova algoritmu, vybírá hrany na základě jejich ceny. Jako chamtivý algoritmus vybere cesty s minimálními náklady.

Příklad Dijkstrova algoritmu

Dijkstrův algoritmus používá k výpočtu celkových nákladů na cestu cenu nebo váhu.

Cílem Dijkstrova algoritmu je minimalizovat tyto celkové náklady nebo hmotnost. Ve výše uvedeném příkladu najdeme nejlepší cesty z uzlu 1 do uzlu 7 a poté spočítáme všechny náklady.

V Dijkstrově algoritmu se najdou nejkratší cesty výpočtem vah. Nebude se hledat všechny možné cesty. Ukažme si Dijkstrův algoritmus na příkladu. Například máte najít nejkratší cestu z uzlu 1 do uzlu 7.

Pro tento proces jsou kroky uvedeny níže:

Krok 1) Inicializujte počáteční cenu uzlu na 0. Přiřaďte „Informace“ ke zbytku uzlů. To znamená, že mezi zdrojem a uzlem neexistuje žádná cesta, nebo cesta ještě nebyla navštívena.

Krok 2) Když vyberete uzel 1, bude označen jako navštívený. Poté aktualizujte všechny sousední uzly uzlu 1. 2, 3, 4 jsou sousední uzly uzlu 1.

Při aktualizaci ceny musíme postupovat podle níže uvedeného postupu:

Náklady každého uzlu můžeme aktualizovat pomocí výše uvedeného vzorce. Například jsme byli v uzlu 1 a potřebovali jsme aktualizovat náklady jeho sousedních uzlů 2, 3, 4. Po aktualizaci budou náklady vypadat takto:

Krok 3) Pro uzel „2“ jsou sousedy 6 a 3. Aktualizujeme cenu na „6“ porovnáním nekonečna (aktuální hodnoty) s cenou uzlu 2 + cena cesty od 2 do 6. Jednoduše řečeno, uzel „6“ bude mít cenu 1 + 3 nebo 4.

Uzel 3 je sousedem uzlu 2. V předchozím kroku jsme však vypočítali jeho cenu, která byla 7. Nyní, pokud je naše cesta 1-2-3, uzel 3 bude mít cenu 10. Cesta 1-2- 3 bude stát 10, zatímco 1 až 3 bude stát 7.

Krok 4) Pro uzel 3 je sousedním uzlem uzel 7. Porovnáním aktuální hodnoty uzlu 7 s cenou cesty (7+1) nebo 8 aktualizujeme cenu uzlu 7. To je 8. Najdeme tedy cestu z uzlu 1 do uzlu 7 a ta je 1→3→7. Cena je 8.

Krok 5) U uzlu 4 aktualizujeme odpovídajícím způsobem cenu jeho sousedního uzlu. Uzel „5“ tedy bude mít aktualizovanou cenu 8. Po krocích 4 a 5 bude vypadat takto:

Cesta 1-3-7 má nyní cenu 8 (dříve). Uzel „7“ nebyl označen jako navštívený, protože k uzlu „7“ se dostaneme z uzlu „6“. Cesta „1-2-6“ měla cenu 4. Cesta 1-2-6-7 tedy bude mít cenu 7.

Protože 7 < 8, nejkratší cesta ze zdrojového vrcholu „1“ do cílového vrcholu „7“ bude 1-2-6-7 a cena je 7. Dříve to bylo 1-3-7 a cena byla 8. Výsledný graf tedy bude vypadat takto:

Hrana označená černou čarou je naše nejkratší cesta od 1 do 7 a bude nás to stát 7.

Nepravý Code Dijkstrův algoritmus

Zde je pseudokód Dijkstrova algoritmu:

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++ Implementace Dijkstrova algoritmu

Implementovat Dijkstrův algoritmus pomocí C++, zde je kód:

#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);
}

Výstup:

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 Implementace Dijkstrova algoritmu

Implementovat Dijkstrův algoritmus pomocí Python, zde je kód:

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)

Výstup:

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

Vidíme, že algoritmus vypočítává nejkratší vzdálenost od zdrojového uzlu.

Aplikace Dijkstrova algoritmu

Dijkstrův algoritmus má širokou škálu využití. Mimo jiné je široce používán v oblasti sítí. Zde je několik reálných použití Dijkstrova algoritmu:

Dijkstra v Google Mapy: Tento algoritmus je základem pro hledání nejkratších cest, jak je vidět z výše uvedeného úryvku kódu.

Google nepoužívá jednoduchý Dijkstrův algoritmus. Místo toho používá jeho upravenou verzi. Když vyberete cíl, zobrazí se vám více cest v Google Mapy. Mezi těmito cestami jsou některé pro uživatele vytříděny. Tyto cesty jsou vybrány na základě „času“. „Čas“ tedy představuje cenu hrany pro nejkratší cestu.

Dijkstra v IP směrování: IP směrování je síťová terminologie. Popisuje, jak je datový paket odesílán příjemci různými cestami. Tyto cesty zahrnují routery, servery a další zařízení. V IP routingu existují různé typy protokolů.

Tyto protokoly pomáhají routeru najít nejkratší cesty pro odeslání dat. Jeden z názvů protokolů je „OSPF (Open Shortest Path First)“. OSPF používá Dijkstrův algoritmus. Router udržuje tabulku tras. Každý router sdílí svou tabulku se sousedními routery. Po obdržení aktualizované tabulky musí znovu vypočítat všechny cesty. V tomto případě router použije Dijkstrův algoritmus.

Omezení Dijkstrova algoritmu

Dijkstrův algoritmus nemůže zaručit nejkratší cestu v grafu se zápornými hranami. Dijkstrův algoritmus se řídí těmito principy:

• Jedna nejkratší cesta bude vedena z jednoho uzlu do druhého.
• Jakmile je vybrána nejkratší cesta mezi dvěma uzly, nebude znovu počítána.

Zde si všimněte dvou příkladů s negativními okraji.

V levém grafu, existují tři vrcholy. Dijkstra bude na grafu fungovat takto:

Krok 1) Počáteční vrchol „1“ bude inicializován na nulu. Ostatní uzly budou mít nekonečno.

Krok 2) Označte uzel „1“ jako navštívený a zařaďte ho do nejkratší cesty.

Krok 3) Vzdálenost zdrojového uzlu 1 k uzlům „2“ a „3“ je nastavena na nekonečno, protože nejkratší cesta teprve musí být vypočítána. Takže jakákoli cesta, která stojí méně než nekonečno, bude přidána k nejkratší cestě (chamtivý přístup).

Krok 4) Aktualizace vzdálenosti od zdrojového vrcholu „1“ na „2“. Aktuální váha bude 5 (5 < nekonečno). Podobně aktualizujte vzdálenost od uzlu „1“ na „3“ s vahou 3.

Krok 5) Pokud nyní zkontrolujeme nejkratší vzdálenosti od uzlu „1“, zjistíme, že 5 je nejkratší vzdálenost pro hranu 1→2. Uzel „2“ bude tedy označen jako navštívený. Podobně bude uzel „3“ také označen jako navštívený, protože nejkratší vzdálenost je 3.

Pokud si ale všimneme, existuje cesta 1-3-2, která bude stát pouze 2. Dijkstra však ukazuje, že z uzlu „1“ do uzlu „2“ je nejkratší vzdálenost 5. Dijkstra tedy nejkratší vzdálenost nevypočítal správně. Důvodem je, že Dijkstra je chamtivý algoritmus. Jakmile je tedy uzel označen jako navštívený, nebude znovu zvažován, i když může být k dispozici kratší cesta. K tomuto problému dochází pouze tehdy, když hrany mají záporné náklady nebo zápornou váhu hran.

Dijkstra v tomto scénáři nedokáže vypočítat nejkratší cestu mezi dvěma uzly. V důsledku toho má tento algoritmus určité nevýhody. K řešení tohoto problému negativních hran se používá jiný algoritmus zvaný „Bellman-Fordův algoritmus“. Tento algoritmus umí pracovat se negativními hranami.

Složitost Dijkstrova algoritmu

Výše uvedená implementace používala dvě smyčky „for“. Tyto smyčky běží pro počet vrcholů. Časová složitost tedy je O(V²)Termín „O“ je zde označení, které udává předpoklad pro Dijkstrův algoritmus.

Graf můžeme uložit pomocí „fronty priorit“. Fronta priorit je binární datová struktura haldy. Bude efektivnější než 2D matice. Hrana s minimálními náklady bude mít vysokou prioritu. Časová složitost pak bude O(E log V). Zde E je počet hran a V je počet vrcholů.

Prostorová složitost je O(V²), protože používáme matici sousednosti (2D pole). Složitost prostoru lze optimalizovat pomocí přilehlého seznamu nebo datové struktury fronty.

Nejčastější dotazy