Bevis för att Dijkstras algoritm terminerar

Är du trött idag? Det finns bara en ifsats.

if distance < neighbor.distance
Vet inte riktigt hur du menar här, men man initierar objekten till oändlig distans (eller något annat stort) och när man beräknar distansen så kommer man att beräkna det optimala värdet. Det är alltså inte så att distansen undan för undan kommer närmre det lägsta värdet, utan minimum kommer på en gång.

oj så mindes jag inte algoritmen ;O
då fattar jag inte. Då kan du väl bara räkna ut antalet gånger som du räknar ut minimumdistanser, när du gjort det för alla så är du klar?

Jag måste på något sätt visa att den inte kan fastna i en loop. Där ligger svårigheten. Det kommer nämligen inte att bli en ny distans för varje pop.

Säg att vi har följande graf. Jag skippar vikterna för enkelhetens skull.

[(0,1),(0,2),(1,3),(2,3),(3,4)]

Vi pushar 0 och kör igång.

0 popas.
distanser får 1 och 2 räknas ut
1 och 2 pushas
1 popas
distans för 0 och 3 räknas ut
3 pushas men ej 0, för den har redan minimal distans
2 popas
distans för 0 och 3 räknas ut
ingenting pushas eftersom 0 och 3 redan har minimal distans
3 popas
distans för 1,2 och 4 räknas ut
4 pushas, men ej 1 och 2
4 popas
ingenting pushas
klar

Vad skulle hända här om 3 inte redan hade minimal distans?

Här menar jag att du inte pushar en ny nod 3 till heapen, väl? Så du borde bara kunna räkna antalet poppade noder, dvs antalet avsökta noder. Och när de är lika med antalet noder i grafen, klar.

Hmm vänta nu, såhär är det väl inte alls. Den blir visst undan för undan bättre, det är därför du har din if-sats.

http://sv.wikipedia.org/wiki/Dijkstras_algoritm

Ja, då hade den pushats. Men detta skulle inte hända. Du säger hela tiden att jag borde kunna göra det och det. Visa hur man gör det istället.
Om jag inte helt är ute och cyklar hade du kunnat använda "if distance < X", där X är den distance som alla noder har initierats till. Här krävs det dock att X är större än alla slutliga värden. Just därför brukar man använda oändligheten.

EDIT
Jag var helt ute och cyklade. Jag kom på att det där även tjänar för kollen om noden är besökt eller inte.

Jag tror du tänker fel på detta, du kommer inte få det minimala avståndet direkt.

Ta grafen {(A, B, 1), (A, C, 2), (B, D, 10), (C, D, 1)}, där sista komponenten är vikten på kanten. Hur skulle algoritmen tilldela sträckorna till D enligt dig?

Jag tycker den bör besöka A -> B när den besöker B så kommer den ta D eftersom det är en granne till B och tilldela den längden 11. Sedan kommer den ta C och ta och tilldela noden D längden 3, dvs D får inte det minsta avståndet direkt. Men jag är inte säker eftersom din pseudokod är lite otydlig i hur den fungerar med avstånden.

Men hursomhelst, om man tar de initiala avstånden till ett stort avstånd (inte oändliga) så bör du kunna ta 2*(summan av avstånden) + (storleken på heapen), om jag inte tänker fel återigen dvs.

Vi börjar alltså i A, så vi pushar den och sätter dist(A)=0

A pop
Sätt d(B)=d(A)+1=1 och d(C)=d(A)+2=2
pusha B och C
B pop
avståndet till A beräknas till 1+d(B)=2 och detta är större än d(A) så inget görs åt A. Sätt d(D)=d(B)+10=12
pusha D
C pop
avståndet till A kastas enligt ovan. Sätt d(D)=d(C)+1=3.

Ja se på fan.



Jag struntade medvetet i hur man räknar ut avståndet, eftersom detta inte ska ha någon betydelse, fast det kanske det har. Mina "avstånd" är sannolikheter så Om vi har grafen [(A,B,0.2),(B,C,0.3),(C,D,0.1)] så är avståndet från A till D 0.1*(1-0.3(1-0.2))

Nja, jag tycker väl inte heller det bör spela roll hur du beräknar avståndet. Men det jag tänkte mest på är att du kan ju räkna ut avståndet oberoende av vilken nod du befinner dig på, då skulle det ju vara skitsamma i vilken ordning man besökte dom. Men eftersom du nu har en avståndsfunktion som beror på vilken nod du befinner dig på så kan du inte förlita dig på att du får minsta avståndet direkt.

Du bör faktiskt kunna begränsa dig till att avståndsfunktionen mappar till naturliga talen (även fast du just nu har en som mappar till reella). Du har ju ändå bara ett ändligt antal olika avstånd du kan få fram, med en rimlig avståndsfunktion dvs, och det är egentligen bara ordningsrelationen som spelar roll och det är ju ganska uppenbart att du kan hitta en funktion som mappar dina avstånd till naturliga talen så att dom bevarar sin ordningsrelation gentemot varandra.

Så jag tror faktiskt mitt förslag på att ha 2(summan av alla avstånd) + (storleken på heapen) som en variant. Där du ser avstånden som naturliga tal.

Kan du utveckla detta lite?

Säg att alla avstånd är naturliga tal. Du initialiserar alla avstånd för noderna till något stort.

Låt nu S = 2*(Summan av alla avstånd som finns lagrad i noderna) + (Storleken på heapen). Med summan av alla avstånd menar jag på alla noder som finns i hela grafen och inte bara de på heapen.

Vid varje iteration kommer du plocka upp någon nod från heapen så S minskar med 1. Om du nu hittar någon granne som du pushar på heapen så måste du åtminstone ha minskat dennes avstånd med 1, så du ökar heapen med 1 men du måste samtidigt åtminstone minska 2*(Summan av alla avstånd) med 2, vilket innebär att S minskar.

Alltså oavsett vad som händer i iterationen så minskar S och den är nedåt begränsad.

Det där kan absolut vara något. Problemet är ju dock fortfarande att jag har reella tal mellan 0 och 1.

Ett tillägg till ovan:
Du visade att ett uträknat värde kan ändras, men jag tror att om en nod har popats så är den minimal. Vad tror du om det?