Előfeltétele, hogy a gráfban nem lehet negatív súlyú él, azaz egy $G : \mathcal{G}_{w}$ gráfra $\forall(u, v) \in G.E$ élre $G.w(u, v) \geq 0$. Azért nem lehet benne negatív súlyú él, mert pl. ha egy csúcshoz megtaláljuk a legrövidebb utat, később a negatív élsúly miatt találnánk hozzá rövidebb utat, de az algoritmus minden csúcsot és minden élt legfeljebb egyszer dolgoz fel.

Működése:

A csúcsokhoz címkéket rendelünk:

• $d$ a start csúcsból mekkora költséggel érhető el az adott csúcs
• $\pi$ az optimális úton melyik csúcsból jutottunk el hozzá, (szülője)

A Dijkstra algoritmus egy mohó algoritmus, minden lépésben azt a csúcsot választja kiterjesztésre, melybe a start csúcsból a legrövidebb utat találta. Ehhez egy minimum prioritásos sort használ segédadatszerkezetként, a prioritásokat minden $v$ csúcsra $d(v)$ értékek adják. Amikor egy csúcs kikerül a sorból, akkor oda már vezet legrövidebb út, ezért a későbbiekben nem kell többet foglalkozni vele. Ha a sorból egy olyan csúcs kerül ki, amelyre igaz, hogy $d(u)=\infty$, az csak akkor lehet, ha nem érhető el a start csúcsból. Ez azonban azt jelenti, hogy a sorban már csak olyan csúcs vagy csúcsok maradtak, amik nem érhetők el a start csúcsból.

Műveletigény:

Az algoritmus futási idejét befolyásolja a prioritásos sor implementációja is. Ha egy csúcshoz jobb utat találunk, mint az eddig kiszámolt, akkor a prioritásos sort is aktualizálni kell.

Ha a prioritásos sort minimum kupaccal valósítjuk meg:

• $n = |G.V|$ (csúcsok száma), $m = |G.E|$ (élek száma)
• $MT(n,m) \in O((n+m) \cdot log \space n)$
• $mT(n,m) \in \Theta(n)$

Egyéb műveletigényei:

Ha a prioritásos sort tömbbel valósítjuk meg:

• $n = |G.V|$ (csúcsok száma), $m = |G.E|$ (élek száma)
• $MT(n,m) \in O(n^2)$, mivel az egész tömböt végig kell nézni

Ha a prioritásos sort Fibonacci kupaccal valósítjuk meg:

• $n = |G.V|$ (csúcsok száma), $m = |G.E|$ (élek száma)
• $MT(n,m) \in O(n \cdot log \space n + m)$

Gyakorlati alkalmazása:

Ez az egyik legnépszerűbb algoritmus. Dijkstra-t használ a Google Maps, social media oldalak használják az ismerős ajánlásokhoz, az OSPF routing protokoll is ezt használja, hogy megtalálja a legjobb útvonalat egy hálózatban stb.