Redigerer Dijkstras algoritme (avsnitt)

== Algoritme == 
La <math>G=(V,E)</math> være en rettet graf, med startnode <math>s</math>. (Hvis grafen er urettet, kan man erstatte hver kant med to kanter - én i hver retning). Vi antar at <math>s</math> har en vei til alle andre noder i <math>G</math>. Hver kant <math>e\in E</math> er en [[tuppel]] <math>e=(u,v)</math> mellom to noder <math>u</math> og <math>v</math>. Hver kant har en lengde <math>l_e</math> som for eksempel kan representere tid, kostnad eller avstand. Det er viktig at  <math>l_e</math> '''ikke''' kan være negativ.

Algoritmen starter med at man merker en distanse <math>dist(u)</math> til hver enkelt node. Avstanden til startnoden settes til null: <math>dist(s)=0</math>. For alle andre noder settes <math>dist(u)=\infty</math>. Man oppretter også et sett <math>S</math> som kommer til å inneholde nodene som vi har funnet den korteste veien til. I begynnelsen er <math>S=\{s\}</math>. For hver node som ''ikke'' er i <math>S</math>, finner vi den korteste veien med følgende metode<ref>Kleinberg, J., & Tardos, E. (2006). ''Algorithm design''. Pearson Education India.</ref>:

# Velg den noden <math>v</math> som det er kortest avstand til fra en node <math>u</math> i <math>S</math>. Det vil si: velg noden hvor <math>dist'(v)=min(dist(u)+l_{(u,v)})</math> er minst mulig. Sett <math>dist(v)=dist'(v)</math>, og legg <math>v</math> til i <math>S</math>, siden vi har funnet den korteste veien til denne noden.
# Fortsett med trinn 1 så lenge det er ubesøkte noder; altså så lenge <math>V - S\neq \emptyset</math>.

Dijkstras algoritme kan også finne korteste vei fra en startnode til en bestemt sluttnode. Da endrer man trinn 2 og terminerer så snart den ønskede sluttnoden har blitt lagt til i <math>S</math>.