Shortest Path First -algoritmi
Dijkstran esittämä Shortest Path First (SPF) -algoritmi laskee tehokkaasti lyhimmän etäisyyden solmusta muihin solmuihin verkossa
Algoritmi toimii seuraavasti:
1. Alusta: tutkitut solmut E = {S}, jäljellä olevat R = {N-S}, O = {kaikki yhden hypyn mittaiset S:stä lähtevät polut } (kunkin polun pituus on kyseisen linkin kustannus)
2. Jos O = Æ tai jos sen ensimmäisen polun pituus on , merkitse kaikki loput R:n solmut saavuttamattomiksi ja lopeta algoritmin suoritus
3. Olkoon P listan O lyhin polku. Poista P O:sta. Olkoon V P:n viimeinen solmu. Jos V jo on E:ssä, jatka kohdasta 2.
4. Luo joukko uusia polkuja lisäämällä P:hen kaikki V:stä lähtevät linkit. Polun pituus = vanha pituus + linkin kust. Lisää polut listaan O pit.järjestykseen, jatka kohdasta 2.