Dijkstruv algoritmus slouzi k nalezeni nejkratsi cesty mezi dvema uzly grafu, resp. k nalezeni nejkratsich cest z daneho uzlu grafu do vsech ostatnich. Vstupem je tedy orientovany ci neorientovany graf s ohodnocenim jednotlivych hran. Je zajimave, ze uvedene dva typy uloh (uzel-uzel, resp. uzel-vsechny uzly) jsou z hlediska asymptoticke casove narocnosti stejne slozite! V obou pripadech je cas vypoctu kvadraticky vzhledem k poctu vrcholu grafu (pouzijeme-li linearni seznam). Pri hledani nejkratsi cesty do jednoho uzlu se totiz chte nechte prubezne pocitaji i nejkratsi cesty do ostatnich uzlu.

Dijkstruv algoritmus:

Vstup: ohodnoceny graf G a pocatecni uzel s

seznam_inicializuj(S)
for each vrchol u do
  found[u]:=False
  dist[u]:=Infinity
  pred[u]:=NIL
  seznam_uloz(S,u)
end for
dist[s]:=0;
while not seznam_prazdny(S) do
  u:=seznam_odeber_min(S)
  for each vrchol v sousedni s u do
    if dist[v]>dist[u]+vaha[u,v] then
      dist[v]:=dist[u]+vaha[u,v]
      pred[v]:=u
    end if
  end for
end while

Vystup: pole dist obsahuje pro kazdy uzel u
                  jeho minimalni vzdalenost od uzlu s
        pole pred obsahuje pro kazdy uzel u
                  jeho bezprostredniho predchudce na nejkratsi ceste z s do u

Poznamka: Dijkstruv algoritmus se nejvice podoba prohledavani do sirky. Rozdil je v tom, ze se vybira jako dalsi vzdy uzel s nejmensi vzdalenosti od vychoziho uzlu s. Proto musime misto fronty pouzit obecny seznam s operaci nalezeni prvku s nejmensi hodnotou. Dalsim podstatnym rozdilem je, ze hodnota dist[u] se neplni jednou jako u BFS, ale snizuje se postupne v nekolika krocich. Ke kazdemu uzlu se tedy nekolikrat vracime, booleanovske pole found[u] z algoritmu BFS zde tedy postrada smysl.