Den "hurtigste korteste sti -algoritme" afhænger meget af de specifikke egenskaber ved din graf:

1. Grafens art:

* vægtet vs. uvægtet: Er kanterne på din graf forbundet med en omkostning eller afstand (vægtet), eller anses alle kanter for at have de samme omkostninger (uvægtet)?

* rettet vs. ikke -rettet: Er kanterne retningsbestemte (envejsgader) eller tovejs (tovejsgader)?

* cyklisk vs. acyklisk: Indeholder grafen cyklusser (stier, der kan føre tilbage til den samme knude)?

* densitet: Er grafen sparsom (relativt få kanter) eller tæt (mange kanter)?

* ikke-negative vægte: Er alle kantvægte ikke-negative? Dette er * afgørende * for mange algoritmer at fungere korrekt. Hvis du har negative vægte, er der behov for særlig håndtering.

* euklidisk vs. ikke-euklidisk: Kan du bruge geometriske egenskaber til at udlede afstande mellem punkter?

2. Målet med algoritmen:

* Enkeltkildes korteste sti: Find den korteste sti fra en specifik startknudepunkt til alle andre noder i grafen.

* Enkelt-destination korteste sti: At finde den korteste sti fra alle knudepunkter til en bestemt destinationsnode (konceptuelt det samme som enkeltkilde, hvis du vender kanternes retning).

* All-par korteste sti: Find den korteste sti mellem * hvert * par knudepunkter i grafen.

* heuristik tilladt? Hvis du har det godt med en tilnærmelse og ikke garanteret den * absolutte * korteste sti, kan du ofte få meget hurtigere resultater med heuristisk søgning.

Her er en sammenbrud af almindelige algoritmer og deres typiske brugssager:

For uvægtede grafer:

* bredde-første søgning (BFS): Dette er den * hurtigste * og enkleste algoritme til uvægtede grafer. Det garanterer at finde den korteste sti (med hensyn til * -nummeret * af kanter) fra en kildeknude til alle andre tilgængelige noder.

* Tidskompleksitet: O (v + e) ​​hvor v er antallet af vertikater, og e er antallet af kanter.

til vægtede grafer med ikke-negative vægte:

* Dijkstra's algoritme: En af de mest anvendte algoritmer til at finde den korteste sti fra en enkelt kilde til alle andre noder i en vægtet graf med * ikke-negative * kantvægte.

* Tidskompleksitet:

* O (v^2) (med en simpel matrix eller listeimplementering for prioriteret kø)

* O (E + V Log V) (ved hjælp af en binær bunke eller prioritetskø)

* O (E + V Log* V) (ved hjælp af Fibonacci -dynger - mindre almindeligt i praksis på grund af overhead)

* a* Søgning: En udvidelse af Dijkstras algoritme, der bruger en * heuristisk * -funktion til at guide søgningen. Det er ofte markant hurtigere end Dijkstra, når du har gode heuristiske oplysninger om den resterende afstand til destinationen.

* Tidskompleksitet: Afhænger af heuristikken. I det bedste tilfælde (perfekt heuristisk) kan det være meget hurtigt. I værste tilfælde (dårlig heuristisk) kan det være så langsomt som Dijkstra's.

* a* kræver en heuristik, der er antagelig (overvurderer aldrig omkostningerne til at nå målet) og konsekvent (monotonisk).

For vægtede grafer med negative vægte (og ingen negative cyklusser):

* Bellman-Ford-algoritme: Kan håndtere grafer med negative kantvægte, så længe der ikke er nogen negative cyklusser (cyklusser, hvor summen af ​​kantvægtene er negativ). Hvis der findes en negativ cyklus, kan den registrere den.

* Tidskompleksitet: O (v * e)

for alle par parters korteste stier:

* Floyd-Warshall-algoritme: Finder den korteste sti mellem * hvert * par af vertices i en rettet eller ikke -rettet graf. Det kan også håndtere negative kantvægte (men ikke negative cyklusser).

* Tidskompleksitet: O (v^3)

* Johnsons algoritme: Kan også finde de korteste stier i par par og kan håndtere negative kantvægte. Det er generelt hurtigere end Floyd-Warshall på * sparsomme * grafer. Det fungerer ved at vægte kanterne for at eliminere negative vægte (ved hjælp af Bellman-Ford) og derefter køre Dijkstras algoritme fra hvert toppunkt.

* Tidskompleksitet: O (v^2 log v + ve)

Sammendragstabel

| Algoritme | Graftype | Kantvægte | Tidskompleksitet | Bemærkninger |

| ------------------ | ------------------------------------------------- | ------------ | -------------------------- | ----------------------------------------------------------------------- |

| BFS | Uvægtet | Ingen | O (V + E) | Hurtigste til uvægtede grafer. |

| Dijkstra's | Vægtet, ikke-negativ | Ikke-negativ | O (E + V Log V) | Fælles, fungerer godt med prioritetskøen. |

| A* | Vægtet, ikke-negativ | Ikke-negativ | Heuristisk afhængig | Kan være meget hurtigere end Dijkstra, hvis der findes en god heuristisk. |

| Bellman-Ford | Vægtet, kan have negative kanter | Enhver | O (v * e) | Kan detektere negative cyklusser. |

| Floyd-Warshall | Vægtet, kan have negative kanter (ingen cyklusser) | Enhver | O (v^3) | De korteste stier med alle par par, gode til tætte grafer. |

| Johnsons | Vægtet, kan have negative kanter (ingen cyklusser) | Enhver | O (V^2 log v + ve) | All-par korteste stier, bedre end Floyd-Warshall til sparsomme grafer |

Praktiske overvejelser og optimeringer:

* datastrukturer: Valget af datastruktur for den prioriterede kø i Dijkstra's algoritme (f.eks. Binær bunke, fibonacci heap) kan påvirke ydeevnen markant, især for store grafer.

* heuristik for en*: At vælge en god heuristik for A* er afgørende. En velvalgt heuristik kan dramatisk fremskynde søgningen. Almindelige heuristik inkluderer euklidisk afstand (til grafer indlejret i et plan) og Manhattan -afstand.

* Grafrepræsentation: Den måde, du repræsenterer din graf på (f.eks. Adjacency -liste, Adjacency Matrix) kan også påvirke ydelsen. Adjacency -lister foretrækkes generelt til sparsomme grafer, mens adjacency -matrixer kan være mere effektive til tætte grafer.

* forarbejdning: For grafer, der er spurgt gentagne gange, kan du forkompuate visse oplysninger (f.eks. Landemærker, korteste sti -træer) for at fremskynde efterfølgende forespørgsler.

* Vejnetværk i den virkelige verden: For vejnet tilbyder specialiserede algoritmer som sammentrækningshierarkier (CH) og tilpasselig ruteplanlægning (CRP) * meget * hurtigere forespørgselstider end generiske algoritmer som Dijkstra's, men de kræver betydelig forarbejdning. Disse bruges ofte i GPS -navigationssystemer.

* Biblioteker: Brug optimerede biblioteker (f.eks. NetworkX i Python, JGrapht i Java), når det er muligt. Disse biblioteker giver ofte stærkt optimerede implementeringer af korteste sti -algoritmer.

I resumé for at bestemme den "hurtigste" algoritme til din situation:

1. Karakteriserer din graf: Er det vægtet, uvægtet, instrueret, sparsom, tæt osv.?

2. Har du brug for enkeltkilde eller alle par korteste stier?

3. er negative kantvægte til stede? I så fald er du begrænset til Bellman-Ford (single-source) eller Johnsons/Floyd-Warshall (alle par).

4. Hvis ikke-negative vægte, skal du overveje Dijkstra's eller A*. Hvis en*, kan du udtænke en god heuristik?

5. For uvægtede grafer er BFS næsten altid det bedste valg.

6. profil og benchmark: Eksperimenter med forskellige algoritmer og datastrukturer for at se, hvad der fungerer bedst på dit specifikke datasæt og hardware.

Vælg den enkleste algoritme, der imødekommer dine behov. Brug ikke Floyd-Warshall, hvis du kun har brug for en enkelt kilde korteste stier.