Den "snabbaste kortaste sökvägsalgoritmen" beror starkt på de specifika egenskaperna för din graf:
1. Grafens natur:
* Viktat kontra ovägt: Betraktas kanterna på din graf förknippad med en kostnad eller avstånd (viktad), eller anses alla kanter ha samma kostnad (ovägda)?
* Regisserad kontra inriktad: Är kanterna riktade (enkelriktade gator) eller dubbelriktade (tvåvägsgator)?
* Cyclic vs. Acyclic: Innehåller grafen cykler (vägar som kan leda tillbaka till samma nod)?
* densitet: Är grafen gles (relativt få kanter) eller täta (många kanter)?
* icke-negativa vikter: Är alla kantvikter icke-negativa? Detta är * avgörande * för många algoritmer att fungera korrekt. Om du har negativa vikter behövs specialhantering.
* euklidisk kontra icke-euklidisk: Kan du använda geometriska egenskaper för att dra slutsatser mellan punkter?
2. Algoritmens mål:
* Single Source kortaste väg: Hitta den kortaste vägen från en specifik startnod till alla andra noder i diagrammet.
* Single-Destination kortaste väg: Hitta den kortaste vägen från alla noder till en specifik destinationsnod (konceptuellt samma som enskild källa om du vänder kanterna riktning).
* Allpar kortaste väg: Hitta den kortaste vägen mellan * varje * par av noder i diagrammet.
* heuristik tillåtet? Om du är okej med en tillnärmning och inte garanterad den * absoluta * kortaste vägen kan du ofta få mycket snabbare resultat med heuristisk sökning.
Här är en uppdelning av vanliga algoritmer och deras typiska användningsfall:
för ovägda grafer:
* Breds-första sökning (BFS): Detta är den * snabbaste * och enklaste algoritmen för ovägda grafer. Den garanterar att hitta den kortaste vägen (i termer av * numret * på kanterna) från en källnod till alla andra nåbara noder.
* Tidskomplexitet: O (V + E) där V är antalet toppar och E är antalet kanter.
För viktade grafer med icke-negativa vikter:
* Dijkstras algoritm: En av de mest använda algoritmerna för att hitta den kortaste vägen från en enda källa till alla andra noder i en vägd graf med * icke-negativa * kantvikter.
* Tidskomplexitet:
* O (V^2) (med en enkel array eller listimplementering för prioriterad kö)
* O (E + V Log V) (med hjälp av en binär hög eller prioritetskö)
* O (E + V Log* V) (med Fibonacci -högar - mindre vanligt i praktiken på grund av omkostnader)
* A* Sök: En förlängning av Dijkstras algoritm som använder en * heuristisk * -funktion för att vägleda sökningen. Det är ofta betydligt snabbare än Dijkstra när du har god heuristisk information om det återstående avståndet till destinationen.
* Tidskomplexitet: Beror på heuristiken. I det bästa fallet (perfekt heuristisk) kan det vara mycket snabbt. I värsta fall (dålig heuristisk) kan det vara lika långsamt som Dijkstra.
* a* kräver en heuristik som är tillåtlig (överskattar aldrig kostnaden för att nå målet) och konsekvent (monoton).
För viktade grafer med negativa vikter (och inga negativa cykler):
* bellman-Ford algoritm: Kan hantera grafer med negativa kantvikter, så länge det inte finns några negativa cykler (cykler där summan av kantvikterna är negativa). Om en negativ cykel finns kan den upptäcka den.
* Tidskomplexitet: O (v * e)
För kortaste vägar:
* Floyd-Warshall-algoritm: Hittar den kortaste vägen mellan * varje * par av hörn i en riktad eller inriktad graf. Det kan också hantera negativa kantvikter (men inte negativa cykler).
* Tidskomplexitet: O (V^3)
* Johnsons algoritm: Kan också hitta kortaste vägar och kan hantera negativa kantvikter. Det är i allmänhet snabbare än Floyd-Warshall på * glesa * grafer. Det fungerar genom att omvända kanterna för att eliminera negativa vikter (med Bellman-Ford) och sedan köra Dijkstras algoritm från varje toppunkt.
* Tidskomplexitet: O (V^2 log v + ve)
Sammanfattningstabell
| Algoritm | Graftyp | Kantvikter | Tidskomplexitet | Anteckningar |
| ------------------ | --------------------------------------------- | ------------ | -------------------------- | --------------------------------------------------------------- |
| BFS | Ovägt | Ingen | O (V + E) | Snabbast för ovägda grafer. |
| Dijkstra's | Vägt, icke-negativ | Icke-negativ | O (E + V Log V) | Vanligt, fungerar bra med prioriterad kö. |
| A* | Vägt, icke-negativ | Icke-negativ | Heuristic-beroende | Kan vara mycket snabbare än Dijkstra om en bra heuristik finns. |
| Bellman-Ford | Vägt, kan ha negativa kanter | Någon | O (v * e) | Kan upptäcka negativa cykler. |
| Floyd-Warshall | Vägt, kan ha negativa kanter (inga cykler) | Någon | O (V^3) | Kortaste vägar i alla par, bra för täta grafer. |
| Johnsons | Vägt, kan ha negativa kanter (inga cykler) | Någon | O (V^2 log v + ve) | Kortaste vägar i alla par, bättre än Floyd-Warshall för glesa grafer |
Praktiska överväganden och optimeringar:
* datastrukturer: Valet av datastruktur för prioriteringskön i Dijkstras algoritm (t.ex. binär hög, Fibonacci -hög) kan påverka prestandan betydligt, särskilt för stora grafer.
* heuristik för en*: Att välja en bra heuristik för en* är avgörande. En väl vald heuristik kan dramatiskt påskynda sökningen. Vanlig heuristik inkluderar euklidiskt avstånd (för grafer inbäddade i ett plan) och Manhattan -avstånd.
* grafrepresentation: Hur du representerar din graf (t.ex. adjacenslista, adjacensmatris) kan också påverka prestandan. Adjektivlistor föredras i allmänhet för glesa grafer, medan adjacensmatriser kan vara mer effektiva för täta grafer.
* Förbehandling: För grafer som ifrågasätts upprepade gånger kan du förekomma viss information (t.ex. landmärken, kortaste vägträd) för att påskynda efterföljande frågor.
* Real-World Road Networks: För vägnätverk erbjuder specialiserade algoritmer som sammandragningshierarkier (CH) och anpassningsbar ruttplanering (CRP) * mycket * snabbare frågetider än generiska algoritmer som Dijkstra, men de kräver betydande förbehandling. Dessa används ofta i GPS -navigationssystem.
* bibliotek: Använd optimerade bibliotek (t.ex. Networkx i Python, Jgrapht i Java) när det är möjligt. Dessa bibliotek ger ofta mycket optimerade implementeringar av kortaste vägalgoritmer.
Sammanfattningsvis för att bestämma den "snabbaste" algoritmen för din situation:
1. Karaktärisera din graf: Är det viktat, ovägt, riktat, gles, tätt osv.?
2. Behöver du kortaste vägar med en enda källa eller alla par?
3. Är negativa kantvikter närvarande? Om så är fallet är du begränsad till Bellman-Ford (Single Source) eller Johnsons/Floyd-Warshall (allpar).
4. Om icke-negativa vikter, överväg Dijkstra eller A*. Om A*, kan du utforma en bra heuristik?
5. För ovägda grafer är BFS nästan alltid det bästa valet.
6. Profil och benchmark: Experimentera med olika algoritmer och datastrukturer för att se vilka som fungerar bäst på ditt specifika datasätt och hårdvara.
Välj den enklaste algoritmen som uppfyller dina behov. Använd inte Floyd-Warshall om du bara behöver kortaste vägar.
