Bellman-Ford

O(V·E)

Bellman-Ford počítá nejkratší cesty z jednoho zdroje relaxací každé hrany v grafu, opakovaně až V−1krát (každá nejkratší cesta má nejvýš V−1 hran). Je pomalejší než Dijkstra, O(V·E), ale na rozdíl od něj funguje se zápornými vahami hran a umí detekovat záporné cykly. Tady jsou váhy kladné vzdálenosti, takže dojde ke stejnému výsledku jako Dijkstra — liší se proces relaxace všech hran.

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. V každém kole relaxuj každou hranu: když je cesta přes u kratší, sniž v.
  3. Opakuj až V−1 kol.
  4. Skonči dřív, jakmile celé kolo nic nezmění.

Pseudokód

1bellmanFord(graph, start):          # O(V·E)2  dist[start] ← 0; all others ← ∞3  repeat V-1 times:4    for every edge (u, v):5      if dist[u] + w(u,v) < dist[v]:6        dist[v] ← dist[u] + w(u,v)    # relax7    stop early if nothing changed