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 Floyd

L’algorithme permet de recherche les plus courts où les plus longs chemins sur un graphe orienté ou non avec des longueurs d’arcs positives ou négatives entre tout couple de sommets.

Algorithme :

$G = <X, U>$ le graphe
$X = \left\lbrace 1, 2, ..., N \right\rbrace$ l’ensemble des sommets du graphe
$U$ l’ensemble des arcs
$N$ le nombre de sommets
$L$ la matrice résultat ( $l_{ij}$ étant la longueur du chemin entre le sommet $i$ et le sommet $j$ )

a) initialisation :

$l_{ij}^{(0)}=$ longueur de l’arc $ij$ si $\left(i, j\right) \in U$
$+\infty$ sinon
$l_{ij}^{(0)} = 0$

b) calcul :

Pour allant de 1 à faire
- $l_{ij}^{k} = min \left( l_{ij}^{k-1}, l_{ik}^{k-1} + l_{kj}^{k-1} \right)$

Exemple :


Graphe orienté pour application de l’algorithme Floyd

$L^{(0)}=$

	1	2	3	4
1	0	3	$+\infty$	3
2	2	0	2	2
3	-2	$+\infty$	0	1
4	$+\infty$	4	4	0

Pour la case 3,2 de la matrice avec $k = 1$ :
$l_{32}^{(1)} = min \left( l_{32}^{(0)}, l_{31}^{(0)} + l_{12}^{(0)} \right) = min \left( +\infty, -2 + 3 \right) = 1$

$L^{(1)}$

	1	2	3	4
1	0	3	$+\infty$	3
2	2	0	2	2
3	-2	1	0	1
4	$+\infty$	4	4	0

Pour la case 1,3 de la matrice avec $k = 2$ :
$l_{13}^{(2)} = min \left( l_{13}^{(1)}, l_{12}^{(1)} + l_{23}^{(1)} \right) = min \left( +\infty, 3 + 2 \right) = 5$

$L^{(2)}$

	1	2	3	4
1	0	3	5	3
2	2	0	2	2
3	-2	$+\infty$	0	1
4	6	4	4	0

$L^{(3)}$

	1	2	3	4
1	0	3	5	3
2	0	0	2	2
3	-2	$+\infty$	0	1
4	2	4	4	0

Et $L^{(4)} = L^{(3)}$

pages : << 1 2 3 4

Poster un message