Dijkstros algoritmas

Algoritmas

Dijkstra algoritmas, kurį sukūrė kompiuterių specialistas Edgaras Dijkstra, sprendžia vieno šaltinio trumpiausių kelių problemą kryptiniame grafe su ne neigiamais kraštinių svoriais.
Pavyzdžiui, jei grafo viršūnės vaizduoja miestus ir kraštinių svoriai vaizduoja atstumą tarp tų miestų, sujungtą tiesioginiu keliu, Djikstros algoritmas naudojamas surasti trumpiausius kelius tarp tų miestų.

Kintamieji:

S - pradžios viršūnė
F - aplankytų viršūnių sąrašas
G - grafas
E - briauna su viršūnėmis (v1,v2)
V - viršūnė
dist(i) - atstumų nuo S iki kiekvienos V masyvas
prev(i) - pointeris į ankstesnes V
i - indeksas
U - neaplankytų viršūnių sąrašas

Pseudokodas:

FOR i=0 to |V|-1
	dist(i)=INFINITY
	prev(i)=NULL
END FOR

WHILE F nepilnas
	imame viršūnę v is U su artimiausiu keliu iki S
	pridedame V į F
	FOR V briaunai(v1,v2)
		IF (dist(v1)+ilgis(v1,v2) < dist(v2)
			dist(v2)=dist(v1)+ilgis(v1,v2)
			prev(v2)=v1
			[galbūt reikia atnaujinti U]
		END IF
	END FOR
END WHILE