Geek or not

Accueil du site > MOCA > Chemins optimaux dans un graphe

Aller à ...

OMFG

Informations

Dans la rubrique MOCA , cet article a été écrit par b3nj et publié le 19 mars 2006.
3074 personnes ont affiché cette page et sa popularité est de 46.

Pebkac

Mots clefs

I see dead pixels.

Outils

SYN

Chemins optimaux dans un graphe

Algorithme de Ford

Cet algorithme permet la recherche du plus court comme du plus long chemin entre un sommet donné et les autres sommets d’un graphe [1]

Algorithme :

$G = <X, \Gamma >$ le graphe
$X = \left\lbrace 1, 2, \ldots, N\right\rbrace$ l’ensemble des sommets du graphe
N le nombre de sommets
P la liste des prédécesseurs
$\Pi$ la liste des distances

Hypothèse :

Le sommet de départ est le sommet 1

a) Initialisation :

$\Pi_{(1)} = 0$
Pour i allant de 2 à N
- $\Pi_{(i)} = + \infty$
Pour i allant de 1 à N
- $P_{(i)} = -1$

b) Calcul :

Pour i allant de 2 à N faire
- $\Pi_{(i)} = min\left( \Pi_{(i)}, min\left( \Pi{(j)} + l_{ij} \right) \right)$ avec $j \in \Gamma_{i}^{-1}$
- Si modifié alors
  - $P_{(i)} = j$

c) Retour :

Recommencer l’étape (b) jusqu’à ce que les $\Pi_{(i)}$ se stabilisent [2]

Exemple :

Voir la figure Exemple de graphe orienté pour recherche de chemins optimaux

Exemple pour $\Pi_{(2)}$ à la première itération de l’algorithme
$\Pi_{(2)} = min\left( \Pi_{(2)}, min\left( \Pi_{(1)} + l_{12}, \Pi_{(3)} + l_{32}, \Pi_{(5)} + l_{52} \right)\right)$ qui donne en fait :
$\Pi_{(2)} = min\left( \infty, min\left( 7, \infty, \infty \right)\right)$

Etape	$P_1$	$P_2$	$P_3$	$P_4$	$P_5$	$P_6$	$\Pi_1$	$\Pi_2$	$\Pi_3$	$\Pi_4$	$\Pi_5$	$\Pi_6$
Initialisation	-1	-1	-1	-1	-1	-1	0	$\infty$	$\infty$	$\infty$	$\infty$	$\infty$
Itération 1	-1	1	1	2	3	2	0	7	1	11	3	8
Itération 2	-1	5	1	5	3	2	0	4	1	8	3	6
Itération 3	-1	5	1	5	3	2	0	4	1	8	3	6

Remarques :

1. Pour calculer les plus longs chemins il convient de modifier l’algorithme de Ford de la façon suivante :

a) Initialisation :

$\Pi_{(1)} = 0$
Pour i allant de 2 à N
- $\Pi_{(i)} = - \infty$
Pour i allant de 1 à N
- $P_{(i)} = -1$

b) Calcul :

Pour i allant de 2 à N faire
- $\Pi_{(i)} = max\left( \Pi_{(i)}, max\left( \Pi{(j)} + l_{ij} \right) \right)$ avec $j \in \Gamma_{i}^{-1}$
Si modifié alors
- $P_{(i)} = j$

c) Retour :
Recommencer l’étape (b) jusqu’à ce que les $\Pi_{(i)}$ se stabilisent.

2. L’existence d’une solution repose sur l’absence de circuit absorbant [3] dans le graphe.


Contre-exemple de graphe pour l’algorithme de Ford

$u_{1} : i \rightarrow k$ n’empruntant pas $\omega$
$l_{(u_{1})} = 7 + 5 = 12$
$u_{2} : i \rightarrow k$ empruntant une fois $\omega$
$l_{(u_{2})} = 9$
On voit bien que $l_{(u_{2})} \langle l_{(u_{1})}$ , ce qui provoque une boucle infinie de l’algorithme.

Faire l’exercice Exercice 9

pages : << 1 2 3 4 >>

[1] Orienté ou pas et comportant des arcs avec des coûts négatifs ou positifs
[2] C’est à dire que la dernière ligne doit être identique à sa ligne précédente
[3] Circuit de longueur négative

Poster un message