Määritelmä
Lyhin polkuongelma on klassinen graafiteoriatutkimuksen algoritmiongelma, jonka tavoitteena on löytää lyhin polku graafin kahden solmun välillä (joka koostuu solmuista ja poluista). Algoritmin erityisiä muotoja ovat:
(1) Lähtöpisteen lyhimmän polun määrittämisen ongelma eli lyhimmän polun löytämisen ongelma, kun aloitussolmu tunnetaan. On sopivaa käyttää Dijkstran algoritmia.
(2) Ongelma lyhimmän polun määrittämisessä päätepisteeseen - toisin kuin aloituspisteen määrittämisessä, tämä ongelma on lyhimmän polun löytäminen, kun loppusolmu tunnetaan. Suuntaamattomassa graafissa tämä ongelma vastaa täysin aloituspisteen määrittämisongelmaa. Suunnatussa graafissa tämä ongelma vastaa ongelmaa määrittää aloituspiste, jossa kaikkien polkujen suunnat ovat käänteisiä.
(3) Ongelma lyhimmän polun määrittämisessä aloituspisteen ja päätepisteen välillä eli alku- ja loppupisteen tiedossa löytää lyhin polku kahden solmun välillä.
(4) Globaali lyhimmän polun ongelma – etsi kaaviosta kaikki lyhimmät polut. On sopivaa käyttää Floyd-Warshall-algoritmia.
Algoritmi
Dijkstra
Etsi lyhin polku yhdestä lähteestä ilman negatiivista painoa. Ajantasaisuus on hyvä, ja ajan monimutkaisuus on O(V*V+E). Jos lähde on tavoitettavissa, O(V*lgV+E*lgV)=>O(E*lgV).
Harvaiden graafien tapauksessa E=V*V/lgV tällä hetkellä, joten algoritmin aikamonimutkaisuus voi olla O(V^2). Jos Fibonacci-pinoa käytetään prioriteettijonona, algoritmin aikamonimutkaisuus on O(V*lgV + E).
Floyd
Etsi lyhin polku useilla lähteillä ja reunoilla ilman negatiivista painoa. Käytä matriisia graafin tallentamiseen. Ajantasaisuus on huono ja ajan monimutkaisuus on O(V^3).
Floyd-Warshall-algoritmi (Floyd-Warshall-algoritmi) on algoritmi, joka ratkaisee lyhimmän polun minkä tahansa kahden pisteen välillä ja joka pystyy käsittelemään oikein suunnatun graafin tai negatiivisen painon lyhimmän polun ongelman.
Floyd-Warshall-algoritmin aikamonimutkaisuus on O(N^3) ja avaruuden kompleksisuus on O(N^2).
Floyd-Warshallin periaate on dynaaminen ohjelmointi:
Oletetaan, että Di,j,k ovat välillä i - j ja vain (1..k) joukon solmut ovat välisolmuja Lyhimmän polun pituus.
Jos lyhin polku kulkee pisteen k kautta, niin Di,j,k = Di,k,k-1 + Dk,j,k-1;
Jos lyhin polku ei kulje pisteen k kautta, Di,j,k = Di,j,k-1.
Siksi Di,j,k = min(Di,k,k-1 + Dk,j,k-1, Di,j,k-1).
Varsinaisessa algoritmissa tilan säästämiseksi iteroi suoraan alkuperäisessä tilassa, jotta tila voidaan pienentää kahteen ulottuvuuteen.
Floyd-Warshall-algoritmin kuvaus on seuraava:
k ← 1 - n do
i ← 1 - n do
j ← 1 - n do
jos (Di,k + Dk,j < Di,j) sitten
Di,j ← Di,k + Dk,j;< /p>
missä Di,j edustaa kustannuksia pisteestä i pisteeseen j, kun Di,j on ∞, se tarkoittaa, että näiden kahden pisteen välillä ei ole yhteyttä.
Bellman-Ford
Jos haluat löytää yksittäisen lähteen lyhimmän polun, voit määrittää, onko negatiivinen painosilmukka (jos on, lyhintä polkua ei ole).
p>Ajantasaisuus on parempi ja ajan monimutkaisuus on O(VE).
Bellman-Ford-algoritmi on algoritmi yhden lähteen lyhimmän polun ongelman ratkaisemiseksi.
Lyhin polkuongelma yhden lähdepisteen kanssa viittaa:
Kun on annettu painotettu suunnattu graafi G ja lähdepiste s, mistä tahansa kuvaajan G pisteestä v, etsi pisteestä s v:n lyhimpään polkuun.
Toisin kuin Dijkstra-algoritmissa, Bellman-Ford-algoritmissa reunapaino voi olla negatiivinen luku.
Kuvittele, että voimme löytää kaaviosta syklin (eli alkaen v:stä ja palaamalla v:ään useiden pisteiden jälkeen) ja tämän syklin kaikkien reunojen painojen summa on negatiivinen. Sitten tämän silmukan kautta lyhin polku kahden silmukan pisteen välillä voi olla äärettömän pieni. Jos tätä negatiivista silmukkaa ei käsitellä, ohjelma jatkuu ikuisesti. Bellman-Ford-algoritmilla on kyky erottaa tämä negatiivinen silmukka.
SPFA
on Bellman-Fordin jonooptimointi, jolla on suhteellisen hyvä ajantasaisuus ja aikamonimutkaisuus O(kE). (K<
on samanlainen kuin Bellman-ford-algoritmi. SPFA-algoritmi käyttää sarjaa relaksaatiooperaatioita saadakseen lyhimmän polun solmusta kaikkiin muihin kaavion solmuihin. Erona on, että SPFA-algoritmi ylläpitää jonoa. Se tekee tarpeettomaksi päivittää muita solmuja heti sen jälkeen, kun solmun nykyinen lyhin polku on päivitetty, mikä vähentää huomattavasti toistuvien toimintojen määrää.
SPFA-algoritmia voidaan käyttää negatiivisilla reunapainoilla varustettuihin kuvaajiin, mikä on sama kuin dijkstra. Algoritmi on erilainen.
Poiketen Dijkstra-algoritmista ja Bellman-ford-algoritmista, SPFA-algoritmin aikatehokkuus on epävakaa, eli eri kaavioiden vaatima aika on hyvin erilainen.< /p>
Parhaassa tapauksessa jokainen solmu jonotetaan vain kerran, jolloin algoritmista tulee itse asiassa leveys-ensimmäinen läpikulku ja sen aikamonimutkaisuus on vain O(E). Toisaalta on olemassa sellaisia esimerkkejä , Joten jokainen solmu jonotetaan (V-1) kertaa. Tällä hetkellä algoritmi degeneroituu Bellman-ford-algoritmiksi ja sen aikamonimutkaisuus on O(VE).
SPFA-algoritmi on negatiivisen reunan painotuskaaviossa Yllä oleva voi korvata täysin Bellman-ford-algoritmin, ja se toimii hyvin myös harvoissa kaavioissa. Ei-negatiivisessa reunapainokaaviossa pahimman tapauksen välttämiseksi käytetään kuitenkin yleensä tehokkaampaa Dijkstra-algoritmia ja sen keon optimointiversiota. Tavallinen SPFA-algoritmi ei toimi tyydyttävästi tietyntyyppisissä ruudukkokaavioissa.