Algorithme de Dijkstra - Licence de mathématiques Lyon...

Algorithme de Dijkstra

Algorithme de Dijkstra

21 octobre 2008

Algorithme de Dijkstra

Introduction

Le but de cette présentation est de faire fonctionnerl’algorithme de Dijkstra sur des exemples concrets.

Exemple 1Cherchons les plus courts chemins d’origine A dans ce graphe:

A

B

E

C

D

10

5

1

9

2

32 4 6

7

Algorithme de Dijkstra

Introduction

Le but de cette présentation est de faire fonctionnerl’algorithme de Dijkstra sur des exemples concrets.

Exemple 1Cherchons les plus courts chemins d’origine A dans ce graphe:

A

B

E

C

D

10

5

1

9

2

32 4 6

7

Algorithme de Dijkstra

Premier exemple

On se place au sommet de plus petit poids, ici le sommet A.

0A

∞B

∞E

∞C

∞D

10

5

1

9

2

32 4 6

7

A B C D E0 ∞ ∞ ∞ ∞•••••

Algorithme de Dijkstra

Premier exemple

On étudie chacune des arêtes partant du sommet choisi.

0A

10B

5

E

∞C

∞D

10

5

1

9

2

32 4 6

7

A B C D E0 ∞ ∞ ∞ ∞• 10A ∞ ∞ 5A••••

Dans les colonnes, on mets la distance à A, et le sommet d’oùl’on vient.

Algorithme de Dijkstra

Premier exemple

On se place de nouveau au sommet de plus petit poids, ici E .

0A

10B

5

E

∞C

∞D

10

5

1

9

2

32 4 6

7

A B C D E0 ∞ ∞ ∞ ∞• 10A ∞ ∞ 5A

• •• •• •• •

Algorithme de Dijkstra

Premier exemple

Et ainsi de suite.

0A

8B

5

E

14C

7D

10

5

1

9

2

32 4 6

7

A B C D E0 ∞ ∞ ∞ ∞• 10A ∞ ∞ 5A

• 8E 14E 7E •• •• •

Algorithme de Dijkstra

Premier exemple

0A

8B

5

E

14C

7D

10

5

1

9

2

32 4 6

7

A B C D E0 ∞ ∞ ∞ ∞• 10A ∞ ∞ 5A

• 8E 14E 7E •• • •• • •

Algorithme de Dijkstra

Premier exemple

0A

8B

5

E

13C

7D

10

5

1

9

2

32 4 6

7

A B C D E0 ∞ ∞ ∞ ∞• 10A ∞ ∞ 5A

• 8E 14E 7E •• 8E 13D • •• • •• • •

Algorithme de Dijkstra

Premier exemple

0A

8B

5

E

13C

7D

10

5

1

9

2

32 4 6

7

A B C D E0 ∞ ∞ ∞ ∞• 10A ∞ ∞ 5A• 8E 14E 7E •• 8E 13D • •• • • •• • • •

Algorithme de Dijkstra

Premier exemple

0A

8B

5

E

9C

7D

10

5

1

9

2

32 4 6

7

A B C D E0 ∞ ∞ ∞ ∞• 10A ∞ ∞ 5A• 8E 14E 7E •• 8E 13D • •• • 9B • •• • • • •

Algorithme de Dijkstra

Premier exemple

0A

8B

5

E

9C

7D

10

5

1

9

2

32 4 6

7

A B C D E0 ∞ ∞ ∞ ∞• 10A ∞ ∞ 5A• 8E 14E 7E •• 8E 13D • •• • 9B • •• • • • •

Si l’on ne considère que les flèches soulignées, on obtient unarbre, un graphe sans cycle.

Algorithme de Dijkstra

Deuxième exemple

Exemple 2Cherchons les plus courts chemins d’origine E dans ce graphe:

E

A

B

C

D

S

3

1

1

3

3

5

1

3

1

Algorithme de Dijkstra

Deuxième exemple

Exemple 2Cherchons les plus courts chemins d’origine E dans ce graphe:

E

A

B

C

D

S

3

1

1

3

3

5

1

3

1

Algorithme de Dijkstra

Deuxième exemple

0E

∞A

∞B

∞C

∞D

∞ S

3

1

1

3

3

5

1

3

1

E A B C D S0 ∞ ∞ ∞ ∞ ∞•••••

Algorithme de Dijkstra

Deuxième exemple

0E

3A

1B

∞C

∞D

∞ S

3

1

1

3

3

5

1

3

1

E A B C D S0 ∞ ∞ ∞ ∞ ∞• 3E 1E ∞ ∞ ∞• •• •• •• •

Algorithme de Dijkstra

Deuxième exemple

0E

2A

1B

4C

6D

∞ S

3

1

1

3

3

5

1

3

1

E A B C D S0 ∞ ∞ ∞ ∞ ∞• 3E 1E ∞ ∞ ∞• 2B • 4B 6B ∞• • •• • •• • •

Algorithme de Dijkstra

Deuxième exemple

0E

2A

1B

4C

6D

∞ S

3

1

1

3

3

5

1

3

1

E A B C D S0 ∞ ∞ ∞ ∞ ∞• 3E 1E ∞ ∞ ∞• 2B • 4B 6B ∞• • • 4B 6B ∞• • • •• • • •

Algorithme de Dijkstra

Deuxième exemple

0E

2A

1B

4C

5

D

7 S

3

1

1

3

3

5

1

3

1

E A B C D S0 ∞ ∞ ∞ ∞ ∞• 3E 1E ∞ ∞ ∞• 2B • 4B 6B ∞• • • 4B 6B ∞• • • • 5C 7C

• • • • •

Algorithme de Dijkstra

Deuxième exemple

0E

2A

1B

4C

5

D

6 S

3

1

1

3

3

5

1

3

1

E A B C D S0 ∞ ∞ ∞ ∞ ∞• 3E 1E ∞ ∞ ∞• 2B • 4B 6B ∞• • • 4B 6B ∞• • • • 5C 7C

• • • • • 6D

Algorithme de Dijkstra

Deuxième exemple

0E

2A

1B

4C

5

D

6 S

3

1

1

3

3

5

1

3

1

E A B C D S0 ∞ ∞ ∞ ∞ ∞• 3E 1E ∞ ∞ ∞• 2B • 4B 6B ∞• • • 4B 6B ∞• • • • 5C 7C• • • • • 6B