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.
4190 personnes ont affiché cette page et sa popularité est de 11.

Pebkac

Mots clefs

I see dead pixels.

Outils

SYN

Chemins optimaux dans un graphe

Algorithme de Dijkstra

Cet algorithme à pour but de réaliser la recherche des plus courts chemins entre un sommet donné et tous les autres sommets du 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
S est l’ensemble des sommets traités
$\overline{S}$ l’ensemble des sommets traités
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 :

$S = \left\lbrace 1 \right\rbrace$
$\overline{S} = X - S = \left\lbrace 2, 3, \ldots, N \right\rbrace$
$\Pi_{(1)} = 0$
$\Pi_{(i)} = l_{1i}$ si $i \in \Gamma_{1}$
$+\infty$ sinon
$P_{(i)} = 1$ si $i \in \Gamma_{1}$
$-1$ sinon

b) Solution :

On sélectionne le sommet $j \in \overline{S}$ tel que $\Pi_{(j)} = min\left(\Pi_{(i)}\right)$ avec $i \in \overline{S}$
$\overline{S} = \overline{S} - \left\lbrace j \right\rbrace$
$S = S + \left\lbrace j \right\rbrace$
Si $\overline{S} = \varnothing$ alors Fin
Sinon aller en (c)

c) Calcul des distances :

Pour tout et Faire
- $\Pi_{(i)} = min \left( \Pi_{( i)}, \Pi_{(j)} + l_{ji} \right)$
- Si $\Pi_{(i)}$ modifié alors $P_{(i)} = j$
retourner en (b)

Exemple :


Exemple de graphe orienté pour exemple de recherche de chemins optimaux

S.S [2]	$S$	$\Pi_{(1)}$	$\Pi_{(2)}$	$\Pi_{(3)}$	$\Pi_{(4)}$	$\Pi_{(5)}$	$\Pi_{(6)}$	$P_{1}$	$P_{2}$	$P_{3}$	$P_{4}$	$P_{5}$	$P_{6}$
1	1	0	7	1	$+\infty$	$+\infty$	$+\infty$	-1	1	1	-1	-1	-1
3	1, 3	0	6	1	$+\infty$	3	8	-1	3	1	-1	3	3
5	1, 3, 5	0	5	1	8	3	8	-1	5	1	5	3	3
2	1, 3, 5, 2	0	5	1	8	3	6	-1	5	1	5	3	2
6	1, 3, 5, 2, 6	0	5	1	8	3	6	-1	5	1	5	3	2
4	1, 3, 5, 2, 6, 4	0	5	1	8	3	6	-1	5	1	5	3	2

$\Pi_{\left(6\right)} = 6$
$P_{\left(6\right)} = 2$
$P_{\left(2\right)} = 5$
$P_{\left(5\right)} = 3$
$P_{\left(3\right)} = 1$
$\Pi_{\left(6\right)} = l_{13} + l_{35} + l_{52} + l_{26}$
$\mu = \left(1, 3, 5, 2, 6\right)$
$l_{\left(\mu\right)} = \Pi_{\left(6\right)} = 6$

Faire l’exercice Exercice 8

pages : << 1 2 3 4 >>

[1] Orienté ou pas, mais ayant des arcs ayant un coût uniquement supérieur à 0
[2] Sommet sélectionné

Poster un message