Dijkstra (nejkratší cesta)

O((V + E) log V)

Dijkstrův algoritmus najde nejkratší cestu ze zdroje do každého dalšího uzlu v grafu s nezápornými vahami hran. Pro každý uzel drží předběžnou vzdálenost a opakovaně finalizuje nejbližší nenavštívený, přičemž relaxuje jeho sousedy (sníží jim vzdálenost, když najde kratší cestu). Tady je váha každé hrany přímá vzdálenost mezi jejími konci, takže táhnutím uzlů měníš ceny. Pohání směrování a hledání nejkratších cest v sítích.

Klik do prázdna = vrchol · klik na 2 vrcholy = hrana · táhni = posuňStart: A
Vstupní graf
Uprav vstup a stiskni Přehrát

Jak to funguje

  1. Nastav vzdálenost startu na 0 a všem ostatním ∞.
  2. Vyber nenavštívený uzel s nejmenší předběžnou vzdáleností a finalizuj ho.
  3. Relaxuj jeho sousedy: když je cesta přes něj kratší, sniž jim vzdálenost a nastav rodiče.
  4. Opakuj, dokud nejsou finalizovány všechny dosažitelné uzly.

Pseudokód

1dijkstra(graph, start):             # O((V+E) log V)2  dist[start] ← 0; all others ← ∞3  while unvisited nodes remain:4    u ← unvisited node with the smallest dist5    for each neighbour v of u:6      if dist[u] + w(u,v) < dist[v]:    # a shorter path7        dist[v] ← dist[u] + w(u,v); parent[v] ← u8    mark u visited                      # dist[u] is now final