|
|
L’algorithme de Dijkstra permet de trouver une chaîne de longueur minimale entre deux sommets d’un graphe pondéré orienté ou non.
Exemple : Plus court chemin de C à I
|
A |
B |
C |
D |
E |
F |
G |
H |
I |
J |
Sél |
Coef |
|
∞ |
∞ |
0 |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
∞ |
C |
0 |
|
4 C |
∞ |
|
10 C |
16 C |
∞ |
∞ |
∞ |
∞ |
∞ |
A |
4 |
|
|
14 A |
|
8 A |
16 C |
14 A |
∞ |
∞ |
∞ |
∞ |
D |
8 |
|
|
14 A |
|
|
16 C |
14 A |
29 D |
∞ |
∞ |
∞ |
B |
14 |
|
|
|
|
|
16 C |
14 A |
29 D |
∞ |
31 B |
24 B |
F |
14 |
|
|
|
|
|
16 C |
|
29 D |
17 F |
31 B |
24 B |
E |
16 |
|
|
|
|
|
|
|
20 E |
17 F |
31 B |
24 B |
H |
17 |
|
|
|
|
|
|
|
20 E |
|
31 B |
22 H |
G |
20 |
|
|
|
|
|
|
|
|
|
31 B |
22 H |
J |
22 |
|
|
|
|
|
|
|
|
|
30 J |
|
I |
30 |