Plus Court Chemin

Question 1

Plus court chemin

Answer 1

Fonction PlusCourtsChemins(g, c, s0)
	Entrée : Un graphe (orienté ou non) g = (S, A) muni d’une fonction de coût c : A → R
		     Un sommet de départ s0 ∈ S
	Sortie : Une arborescence des plus courts chemins partant de s0
	     	 Un tableau d tel que ∀si ∈ S, d[si ] = δ(s0, si )

Question 2

Coût d’un plus court chemin

Answer 2

δ(si , sj ) = +∞ s′il n′existe pas de chemin de si vers sj
δ(si , sj ) = −∞ s′il existe un circuit absorbant
δ(si , sj ) = min{c(p)|p = chemin de si a sj} sinon

Question 3

Principe d’optimalité d’une sous structure

Answer 3

Tout sous-chemin d’un plus court chemin est un plus court chemin :

Soit p =< s0, s1, . . . , sk > un plus court chemin
∀i, j tel que 0≤ i < j ≤ k : pij = <si , si+1, ... , sj> 
est un plus court chemin

Question 4

Pré conditions pour la recherche de plus court chemin

Answer 4

Principe d’optimalité d’une sous structure
Pas de circuit absorbant

Question 5

Plus court chemin à origine unique

Answer 5

Dijkstra, TopoDAG et Bellman-Ford

Question 6

Tableaux utilisés quand plus courts chemins

Answer 6

Tableau π tq π[s0] = null et π[sj ] = si si si → sj est un arc de l’arbo.
Rm : ∀si ∈ S, π[si ] 6 = null ⇒ δ(s0, si ) = δ(s0, π[si ]) + c(π[si ], si )

Question 7

Relâcher un arc

Answer 7

Proc relacher((si , sj ), π, d)
	Entrée : Un arc (si , sj )
	Entrée/Sortie : Les tableaux π et d
	Précond. : d[si ] ≥ δ(s0, si ) et d[sj ] ≥ δ(s0, sj )
	Postcond. : δ(s0, sj ) ≤ d[sj ] ≤ d[si ] + c(si , sj )
2 	début
3 		si d[sj ] > d[si ] + c(si , sj ) alors
4 			d[sj ] ← d[si ] + c(si , sj )
5 			π[sj ] ← s

Question 8

Algorithme de Dijkstra

Answer 8

Précondition :
L’ajout d’un arc (i , j) à un chemin s0 -> i ne peut que dégrader son coût + tous les coûts sont positifs

 Fonction Dijkstra(g, c, s0)
2 	pour chaque sommet si ∈ S faire
3		d[si ] ← +∞ ; π[si ] ← null ; Colorier si en blanc
4 	d[s0] ← 0 ; Colorier s0 en gris
5 	tant que il existe un sommet gris faire
6 		Soit si le sommet gris tq d[si ] soit minimal
7 		pour tout sommet sj ∈ succ(si ) faire
8 			si sj est blanc ou gris alors
9 				relacher((si , sj ), π, d)
10 				si sj est blanc alors colorier sj en gris;
11 		Colorier si en noir
12 	retourne π et d

Question 9

Complexité de Dijkstra

Answer 9

O(n^2) si recherche linéaire du sommet gris minimisant d (ligne 6)
O((n + p)log(n)) si les sommets gris sont stockés dans un tas binaire

Question 10

Algorithme TopoDAG

Answer 10

1 Fonction TopoDAG(g, c, s0)
	Précond. : g est un DAG
2 	pour chaque sommet si ∈ S faire
3		d[si ] ← +∞
4 		π[si ] ← null
5 	d[s0] ← 0
6 	Trier topologiquement les sommets de g à l’aide d’un DFS partant de s0
7 	pour chaque sommet si pris selon l’ordre topologique faire
8 		pour chaque sommet sj ∈ succ(si ) faire relacher((si , sj ), π, d);
9 	retourne π et d

Question 11

Complexité TopoDAG

Answer 11

O(n + p)

Question 12

Algorithme de Bellman-Ford

Answer 12

Fonction Bellman-Ford(g, c, s0)
2 	pour chaque sommet i ∈ S faire
3 		d[i] ← +∞
4 		π[i] ← null
5 	d[s0] ← 0
6 	pour k variant de 1 à #S − 1 faire
7 		pour chaque sommet i ∈ S faire
8 			pour chaque sommet j ∈ pred(i) faire relacher((i, j), π, d);
9 	retourne π et d

Question 13

Complexité Bellman-Ford

Answer 13

O(np)

Question 14

Plus court chemin entre tout couple de sommets

Answer 14

On utilise Floyd-Warshall

Question 15

Algorithme de Floyd-Warshall

Answer 15

1 Fonction Floyd-Warshall(g, c)
2 	pour chaque couple de sommets (i, j) ∈ S × S faire
3 		si (i, j) ∈ A alors d[0][i][j] ← c[i][j];
4 		sinon d[0][i][j] ← +∞;
5 	pour k variant de 1 à n faire
6 		pour chaque couple de sommets (i, j) ∈ S × S faire
7 			d[k][i][j] ← min(d[k − 1][i][j], d[k − 1][i][k] + d[k − 1][k][j])
8 	retourne d[n]

Question 16

Complexité de Floyd-Warshall

Answer 16

O(n^3)

Question 17

Recherche d’un meilleur chemin

Answer 17

Extensions
- Dijkstra : chemin le plus probable/maximisant le coût de son plus petit arc
- TopoDAG : Recherche d’un plus long chemin
- BF & FW : Chemin maximisant la somme/le produit des coûts