Definice
Problém s nejkratší cestou je klasickým algoritmickým problémem ve výzkumu teorie grafů, jehož cílem je najít nejkratší cestu mezi dvěma uzly v grafu (složeném z uzlů a cest) . Mezi specifické formy algoritmu patří:
(1) Problém určení nejkratší cesty výchozího bodu – tedy problém nalezení nejkratší cesty, když je znám výchozí uzel. Vhodné je použít Dijkstrův algoritmus.
(2) Problém určení nejkratší cesty ke koncovému bodu - na rozdíl od problému určení počátečního bodu je tento problém problémem nalezení nejkratší cesty, když je znám koncový uzel. V neorientovaném grafu je tento problém zcela ekvivalentní problému určení výchozího bodu. V orientovaném grafu je tento problém ekvivalentní problému určení počátečního bodu, ve kterém jsou směry všech cest obráceny.
(3) Problém určení nejkratší cesty mezi počátečním a koncovým bodem – to znamená, že při znalosti počátečního a koncového bodu najdeme nejkratší cestu mezi dvěma uzly.
(4) Globální problém nejkratší cesty – najděte všechny nejkratší cesty v grafu. Je vhodné použít Floyd-Warshall algoritmus.
Algoritmus
Dijkstra
Najděte nejkratší cestu s jedním zdrojem a bez záporné váhy. Včasnost je dobrá a časová složitost je O(V*V+E). Pokud je zdroj dosažitelný, O(V*lgV+E*lgV)=>O(E*lgV).
V případě řídkých grafů je v tuto chvíli E=V*V/lgV, takže časová složitost algoritmu může být O(V^2). Pokud je Fibonacciho zásobník použit jako prioritní fronta, je časová složitost algoritmu O(V*lgV + E).
Floyd
Najděte nejkratší cestu s více zdroji a hranami bez záporné váhy. K zaznamenání grafu použijte matici. Včasnost je špatná a časová složitost je O(V^3).
Algoritmus Floyd-Warshall (algoritmus Floyd-Warshall) je algoritmus pro řešení nejkratší cesty mezi libovolnými dvěma body, který dokáže správně zpracovat problém s nejkratší cestou orientovaného grafu nebo záporné váhy.
Časová složitost Floyd-Warshallova algoritmu je O(N^3) a prostorová složitost je O(N^2).
Principem Floyd-Warshall je dynamické programování:
Předpokládejme, že Di,j,k jsou od i do j a pouze uzly v množině (1..k) jsou mezilehlé uzly Délka nejkratší cesty.
Pokud bodem k prochází nejkratší cesta, pak Di,j,k = Di,k,k-1 + Dk,j,k-1;
Pokud nejkratší cesta neprochází bodem k, pak Di,j,k = Di,j,k-1.
Proto Di,j,k = min(Di,k,k-1 + Dk,j,k-1, Di,j,k-1).
Ve skutečném algoritmu, abyste ušetřili místo, iterujte přímo v původním prostoru, aby bylo možné prostor zmenšit na dva rozměry.
Popis algoritmu Floyd-Warshall je následující:
pro k ← 1 až n do
pro i ← 1 až n do
pro j ← 1 až n do
if (Di,k + Dk,j < Di,j) pak
Di,j ← Di,k + Dk,j;< /p>
kde Di,j představuje náklady z bodu i do bodu j, když Di,j je ∞, znamená to, že mezi těmito dvěma body není žádné spojení.
Bellman-Ford
Chcete-li najít nejkratší cestu jednoho zdroje, můžete určit, zda existuje záporná smyčka váhy (pokud existuje, neexistuje žádná nejkratší cesta),
p>Včasnost je lepší a časová složitost O(VE).
Algoritmus Bellman-Ford je algoritmus pro řešení problému nejkratší cesty z jednoho zdroje.
Problém s nejkratší cestou s jedním zdrojovým bodem se týká:
Za předpokladu váženého orientovaného grafu G a zdrojového bodu s pro libovolný bod v v grafu G najděte od s do Nejkratší cestu v.
Na rozdíl od Dijkstrova algoritmu může být v Bellman-Fordově algoritmu váha hrany záporné číslo.
Představte si, že z grafu najdeme cyklus (tj. začíná od v a po několika bodech se vrací k v) a součet vah všech hran v tomto cyklu je záporný. Potom prostřednictvím této smyčky může být nejkratší cesta mezi libovolnými dvěma body smyčky nekonečně malá. Pokud se tato negativní smyčka nevyřeší, program poběží navždy. Algoritmus Bellman-Ford má schopnost rozlišit tuto negativní smyčku.
SPFA
je optimalizace fronty společnosti Bellman-Ford s relativně dobrou aktuálností a časovou složitostí O(kE). (K<
je podobný Bellman-fordovu algoritmu. Algoritmus SPFA používá řadu relaxačních operací k získání nejkratší cesty z uzlu ke všem ostatním uzlům v grafu. Rozdíl je v tom, že algoritmus SPFA udržuje frontu, takže není nutné aktualizovat další uzly ihned po aktualizaci aktuální nejkratší cesty uzlu, čímž se výrazně snižuje počet opakovaných operací.
Algoritmus SPFA lze použít pro grafy se zápornými váhami hran, což je stejné jako u dijkstra Algoritmus je odlišný.
Na rozdíl od Dijkstrova algoritmu a Bellman-fordova algoritmu je časová účinnost algoritmu SPFA nestabilní, to znamená, že čas potřebný pro různé grafy je velmi odlišný.< /p>
V nejlepším případě je každý uzel zařazen do fronty pouze jednou, pak se algoritmus ve skutečnosti stává procházením do šířky a jeho časová složitost je pouze O(E). Na druhou stranu existují takové příklady, takže každý uzel je zařazen do fronty (V-1) krát. V tomto okamžiku algoritmus degeneruje na Bellman-fordův algoritmus a jeho časová složitost je O(VE).
Algoritmus SPFA je v grafu záporné váhy hran Výše uvedené může zcela nahradit Bellman-fordův algoritmus a také funguje dobře v řídkých grafech. Aby se však předešlo nejhoršímu případu, v nezáporném grafu váhy hran se obvykle používá efektivnější Dijkstrův algoritmus a jeho verze s optimalizací haldy. Obvyklý algoritmus SPFA nefunguje uspokojivě v typu mřížkového grafu.