Geek or not

Aller à ...

OMFG

Informations

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

Pebkac

Mots clefs

Dijkstra

I see dead pixels.

Outils

SYN

Exercice 8

Réponses

SS	$\Pi_{0}$	$\Pi_{1}$	$\Pi_{2}$	$\Pi_{3}$	$\Pi_{4}$	$\Pi_{5}$	$\Pi_{6}$	$\Pi_{7}$	$\Pi_{8}$	$\Pi_{9}$	$P_{0}$	$P_{1}$	$P_{2}$	$P_{3}$	$P_{4}$	$P_{5}$	$P_{6}$	$P_{7}$	$P_{8}$	$P_{9}$
0	0	4	1	3	$\infty$	$\infty$	$\infty$	$\infty$	$\infty$	$\infty$	-1	0	0	0	-1	-1	-1	-1	-1	-1
2	0	4	1	2	8	7	$\infty$	$\infty$	$\infty$	$\infty$	-1	0	0	2	2	2	-1	-1	-1	-1
3	0	4	1	2	8	4	5	4	$\infty$	$\infty$	-1	0	0	2	2	3	3	3	-1	-1
1	0	4	1	2	7	4	5	4	$\infty$	$\infty$	-1	0	0	2	1	3	3	3	-1	-1
5	0	4	1	2	7	4	5	4	8	$\infty$	-1	0	0	2	1	3	3	3	5	-1
7	0	4	1	2	7	4	5	4	8	6	-1	0	0	2	1	3	3	3	5	7
6	0	4	1	2	7	4	5	4	8	6	-1	0	0	2	1	3	3	3	5	7
9	0	4	1	2	7	4	5	4	8	6	-1	0	0	2	1	3	3	3	5	7
4	0	4	1	2	7	4	5	4	8	6	-1	0	0	2	1	3	3	3	5	7
8	0	4	1	2	7	4	5	4	8	6	-1	0	0	2	1	3	3	3	5	7

$\Pi_{(9)} = 6$
$P_{(9)} = 7$
$P_{(7)} = 3$
$P_{(3)} = 2$
$P_{(2)} = 0$
$\Pi_{(9)} = l_{02} + l_{23} + l_{37} + l_{79}$
$\mu = \left( 0, 2, 3, 7, 9 \right)$
$l_{\mu} = \Pi_{(9)} = 6$


Réponse à la question 3 de l’exercice 8

Les valeurs réelles sont les suivantes :

$1 \rightarrow 2 = 3$
$1 \rightarrow 4 = 7$
$1 \rightarrow 3 = 1$

Et si on applique l’algorithme de Dijkstra

	$\Pi_{1}$	$\Pi_{2}$	$\Pi_{3}$	$\Pi_{4}$
1	0	3	2	$\infty$
3	0	3	2	$\infty$
2	0	3	2	7
4	0	3	2	7

On voit bien que sur la dernière ligne la distance entre le sommet 4 et le sommet 2 n’est pas calculée car le sommet 2 à déjà été sélectionné.

4. A remplacer dans l’algorithme :

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 $X_{k} \in S$ alors Fin
Sinon aller en (c)
pages : << 1 2

Poster un message