Algoritmul lui Dijkstra determină câte un drum de cost minim de la vârful sursă x0, la fiecare dintre celelalte vârfuri ale grafului.
Iniţial, singurul vârf pentru care drumul de cost minim este deja cunoscut este numai vârful sursă x0.
La fiecare pas se va selecta un vârf, care nu a mai fost selectat şi care se află la distanţă minimă de mulţimea vârfurilor selectate (cele pentru care drumul de cost minim este deja determinat).
Distanţa de la mulţimea vârfurilor deja selectate (să o notăm M) la un vârf oarecare yeste egală cu costul drumului de cost minim de la vârful sursă x0 la y, drum care trece numai prin vârfuri din mulţimea M.
După selectarea vârfului situat la distanţă minimă de M (fie acesta y), toate distanţele de la M la vârfurile neselectate trebuie actualizate.
Mai exact, să notăm d[z] distanţa de la vârful neselectat z la mulţimea M, înainte de selectarea vârfului y.
Prin includerea vârfului y în mulţimea M este posibil să obţinem un drum de cost mai mic, dacă distanţa d[z] este mai mare decât distanţa până la vârful y (d[y]) +costul arcului (y, z), adică d[z]>d[y]+c[y][z]. În acest caz, distanţa de la mulţimea M la vârful z trebuie actualizată.
Pentru a putea reconstitui şi drumurile de cost minim, vom reţine pentru fiecare vârf ydin graf (exceptând vârful x0) vârful care îl precedă pe drumul de cost minim de la x0la y.
În animaţie, observaţi că vârfurile incidente cu arcele roşii aparţin mulţimii M (au fost selectate) iar extremităţile finale ale arcelor verzi sunt vârfurile către care s-a făcut actualizarea şi care sunt luate în calcul pentru selectare la următorul pas.
C++
void dijkstra(int x0)
{
int i, j, min, k, ok;
int viz[NMAX], d[NMAX], tata[NMAX];
for (i = 1; i<=n; i++) {
d[i] = C[x0][i];
tata[i] = x0;
viz[i] = 0;
}
tata[x0] = 0;
viz[x0] = 1; ok = 1;
while (ok) {
min = INFINIT;
for (i = 1; i<=n; i++)
if (!viz[i] && min>d[i]) {
min = d[i];
k = i;
}
if (min != INFINIT) {
viz[k] = 1;
for (i = 1; i<=n; i++)
if (!viz[i] && d[i]>d[k]+C[k][i]) {
d[i] = d[k]+C[k][i];
tata[i] = k;
}
}
else ok = 0;
}
}