Structures de données IFT-10541 Abder Alikacem Trace de l’algorithme de Dijkstra Département...

Structures de donnéesIFT-10541

Abder AlikacemAbder Alikacem

Trace de l’algorithme deDijkstra

Département d’informatique et de génie logiciel

Édition Septembre 2009

Plus court chemin sans poids

V0 V1

V3V2

V5 V6

V4

origine

0

File: V2

Plus court chemin sans poids

V0 V1

V3V2

V5 V6

V4

origine

1

1

File: V0 V5

Plus court chemin sans poids

V0 V1

V3V2

V5 V6

V4

origine

1

1

2

2

File: V5 V1 V3

Plus court chemin sans poids

V0 V1

V3V2

V5 V6

V4

origine

1

1

2

2

File: V1 V3

Plus court chemin sans poids

V0 V1

V3V2

V5 V6

V4

origine

1

1

2

2

File: V3 V4

3

Plus court chemin sans poids

V0 V1

V3V2

V5 V6

V4

origine

1

1

2

2

File: V4 V6

3

3

Plus court chemin sans poids

V0 V1

V3V2

V5 V6

V4

origine

1

1

2

2

File: V6

3

3

Plus court chemin sans poids

V0 V1

V3V2

V5 V6

V4

origine

1

1

2

2

File: vide

3

3

Algorithme de Dijkstra

V0 V1

V3V2

V5 V6

V4

origine

0

File de priorité: (V0,0)

4

2

1

2 2

103

64

8

1

5

0

,0)

Algorithme de Dijkstra

V0 V1

V3V2

V5 V6

V4

0

4

2

1

2 2

103

64

8

1

5

origine0

File de priorité: (V3 ,1) (V1 ,2)

1

2

Algorithme de Dijkstra

V0 V1

V3V2

V5 V6

V4

0

File de priorité: (V1 ,2) (V4 ,3) (V2 ,3) (V6 ,5) (V5 ,9)

4

2

1

2 2

103

64

8

1

5

origine0

13

9 5

3

2

Algorithme de Dijkstra

V0 V1

V3V2

V5 V6

V4

0

File de priorité: (V4 ,3) (V2 ,3) (V6 ,5) (V5 ,9)

4

2

1

2 2

103

64

8

1

5

origine0

13

9 5

3

2

Algorithme de Dijkstra

V0 V1

V3V2

V5 V6

V4

0

File de priorité: (V2 ,3) (V6 ,5) (V5 ,9)

4

2

1

2 2

103

64

8

1

5

origine0

13

9 5

3

2

Algorithme de Dijkstra

V0 V1

V3V2

V5 V6

V4

0

File de priorité: (V6 ,5) (V5,8) (V5 ,9)

4

2

1

2 2

103

64

8

1

5

origine0

13

8 5

3

2

Algorithme de Dijkstra

V0 V1

V3V2

V5 V6

V4

0

File de priorité: (V5 ,6), (V5 ,8) (V5 ,9)

4

2

1

2 2

103

64

8

1

5

origine0

13

6 5

3

2

Algorithme de Dijkstra

V0 V1

V3V2

V5 V6

V4

0

File de priorité: (V5 ,8) (V5 ,9)

4

2

1

2 2

103

64

8

1

5

origine0

13

6 5

3

2

Algorithme de Dijkstra

V0 V1

V3V2

V5 V6

V4

0

Résultat final

4

2

1

2 2

103

64

8

1

5

origine0

13

6 5

3

2

Algorithme de Dijkstra

3 tableaux• Distance•Distance[j] représente à chaque instant la distance de j à Sa.

• Chemin•Chemin[j] représente le prédécesseur de j

• Sa

• Sa[j] indique si « j » fait parti ou non de Sa.

Algorithme de Dijkstra