lyndamigri
Messages postés5Date d'inscriptionlundi 5 avril 2010StatutMembreDernière intervention 4 octobre 2010
-
15 avril 2010 à 19:22
masoantoko
Messages postés9Date d'inscriptionjeudi 15 avril 2010StatutMembreDernière intervention22 avril 2010
-
17 avril 2010 à 23:41
Bonjour j'ai un algorithme de djikstra suivent et je sait pas appliquer en php aide moi svp
les données
En entrée
X : ensemble des sommets
U : ensemble d’arcs sous forme (x ,y) (les jointures entre différents ville=route)
P : un vecteur de n éléments ou P[i] représente le poids de sommet i dan le réseau
r : un sommet donné de X
En sortie :
π : vecteur de n éléments. Chaque entrée π(x) représente le poids du chemin optimal de r ver x
S : ensemble des sommets qui sont extrémité terminale d’un chemin commençant par r.
Autre :
Fait : vecteur de n éléments. chaque entrée t[k] contient un sommet de X .le vecteur fait à la fin sera trié dans un ordre croissant par rapport aux valeur de π[fait [k]].
I(u) : donne l’extrémité initiale de l’arc u .T[u] : donne l’extrémité terminal de l’arc u .
Algorithme 3 Algorithme de Djikstra
Début
S←{r}
k←1
fait [k]←r
pour tout x∈X faire π[x]←+∞ fait
π[r]←0
tant que (k<n) et (π[x]<+∞)
faire
pour tout u∈U / (I(u)=fait [k]) et (T(u)∉ s)
faire
x=T(u)
π(x)←min { π[x],π[fait[k]]+p[u]}
fait
x ←y / y ∈ X-S et π[y]minimal
k←k+1
fait[k] ←x
S←S ∪{x}
Fait
Fin