ALGORITHME DE DJIKSTRA

Question

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&#8217;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 :
&#960; : vecteur de n éléments.  Chaque  entrée &#960;(x) représente le poids du chemin optimal de r ver x
S : ensemble des sommets qui sont extrémité terminale d&#8217;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 &#960;[fait [k]].
I(u) : donne l&#8217;extrémité initiale de l&#8217;arc u .T[u] : donne l&#8217;extrémité terminal de l&#8217;arc u .
Algorithme 3 Algorithme de Djikstra
Début
  S&#8592;{r}
k&#8592;1
fait [k]&#8592;r
pour  tout  x&#8712;X  faire  &#960;[x]&#8592;+&#8734; fait
&#960;[r]&#8592;0
tant que (k<n) et (&#960;[x]<+&#8734;)
faire
     pour  tout  u&#8712;U / (I(u)=fait [k])  et (T(u)&#8713; s)
   faire
    x=T(u)
    &#960;(x)&#8592;min { &#960;[x],&#960;[fait[k]]+p[u]}
   fait
     x &#8592;y / y &#8712; X-S et &#960;[y]minimal
     k&#8592;k+1
     fait[k] &#8592;x
    S&#8592;S &#8746;{x}
           Fait
Fin

JulSoft · Answer

J'avais codé un truc du genre à l'époque (en C# aussi...). Je vais fouiller dans mes archives, traduire en php et je te passe ça des que je l'ai.

lyndamigri · Answer

merci d'avance aide moi plaise.

masoantoko · Answer

salut moi aussi j'ai un projet qui cherche un chemin plus court sur un trajet de bus en php, vous pouvez m'aidez?
Merci d'avance..

ALGORITHME DE DJIKSTRA

3 réponses

Votre réponse

Discussions similaires