Dijkstrin algoritam
Dijkstrin algoritam, koji je dobio ime po nizozemskom informatičaru Edsgeru Dijkstri, služi za nalaženje najkraćeg puta u usmjerenom grafu s nenegativnim vrijednostima rubova.
Na primjer, ako čvorove predstavimo kao gradove, a vrijednosti rubova kao udaljenosti između onih gradova koji su direktno povezani, Dijkstrin algoritam nalazi najkraći put između dva grada.
Neka je dat težinski usmjereni graf G i početni čvor s iz G. Ako skup svih čvorova grafa obilježimo s V, skup rubova s E, tada je svaki rub iz E, predstavljena parom čvorova (u,v) koje ona povezuje iz V. Također, neka svaki rub dobije određenu vrijednost (težinu) w. Težina svakog ruba se može predstaviti kao udaljenost između dva čvora koje ona povezuje. Dužina puta između dva čvora je suma težina rubova na tom putu. Za dati par čvorova s i t iz V, Dijkstrin algoritam nalazi vrijednost najkraćeg puta. Česta je njegova upotreba za nalaženje najkraćeg puta od čvora s do svih ostalih iz skupa V.
