modélisation numérique d'un lieu public

je vais essayer de faire des graphes avec les algorithmes pour mieu comprendre.

ouais ce serait vraiment sympa de ta part!

Soit S l'ensemble des sommets pour
lequel y aboutissant de X0.

Le cardinal de S augment d'une unité a chaque etiration.

Les sommets s’introduise dans S suivant l’ordre de leur plus courte distance de
X0, cad si S={X0, Xi, Xj, Xk} alors ∏(X0)
<= ∏(Xi) <= ∏(Xj) <= ∏(Xk).


Soit Xp un sommet qu’on nome
sommet pivot.


Etape
0 : S={X0}


Xp = X0



∏(X0) = 0



∏(X) = +∞ quelque soit X ≠ X0


Etape
1 : tant que (S ≠ X et ∏(Xp) < +∞)


{Quelque soit u € U / I (u)
= Xp


Si (T(u) n’appartient
pas S) alors{X=T(u)


Si
(∏(X)> ∏(Xp) + d(u))


Alors
∏(X) = ∏(Xp) + d(u)


}


Choisir X n’appartient pas S /
min ∏(X)


Xp = x ; S=S U {x}


Aller à (1)


}

exemple d'un graphe:

appliction de l'algorithme sur le graphe precedent :

S = {X0}

Xp=X0 : (0,1) ∏(X1)> ∏(X0)+3 => ∏(X1) = 3
(0,4) ∏(X4)> ∏(X0)+2 => ∏(X1) = 2

Xp=X4 : S={X0,X4}
(4,3) ∏(X3)> ∏(X4)+1 => ∏(X3) = 3

Xp=X1 : S={X0,X4,X1}
(1,2) ∏(X2)> ∏(X1)+2 => ∏(X2) = 5
(1,5) ∏(X5)> ∏(X1)+2 => ∏(X5) = 5

Xp=X3 : S={X0,X4,X1,X3}
(3,2) ∏(X2)> ∏(X3)+2 => faux
(3,5) ∏(X5)> ∏(X3)+3 => faux
(3,6) ∏(X6)> ∏(X3)+6 => ∏(X6) = 9

Xp=X2 : S={X0,X4,X1,X3,X2}
(2,5) ∏(X5)> ∏(X2)+1 => faux

Xp=X5 : S={X0,X4,X1,X3,X2,X5}
(5,6) ∏(X6)> ∏(X5)+2 => ∏(X6) = 7


Xp=X5 : => S=X
Arret.


Le plus court chemin de X0 a X6 :
X0,X1,X5,X6 de longeur 7.

pouvez vous m'expliquez le role de cette algorithme

salut;
c'est un algorithme de recherche du plus court chemin.
dans cette exemple en cherche le plus court chemin de 1 à 6.

merci zied pour l'explication

vraiment génial, merci pour l'exemple concret!

de rien mes amis.
et attendez l'exemple des autres algorithmes.

Milles merci Zied .

Merci Zied86