Djikstra : implémentation avec une matrice d'adjacence
Bonjour,
J'ai quelques questions sur l'implémentation de l'algorithme de Djikstra.
Actuellement je représente mon graphe par une matrice adjacente (tableau a deux dimensions).
Si j'ai un arc présent entre un sommet a et un sommet b, alors graph[a][b] est mis à 1 sinon la case contient 0.
La distance entre chacun de mes arcs vaut également 1 (lorsque deux sommets sont reliés), le graph[a][b] == 1 représente donc également le poids (la distance) entre l'arc A et B.
L'algorithme est le suivant :
Citation:
Relax( u , v , w )
SI d[v] > d[u] + w(u,v) alors
d[v] <- d[u] + w(u,v)
pred(v) <- u
FIN SI
Dijkstra( G , s , w )
Init(G,s)
E <- Ensemble vide
F <- tous les sommets de G
TANT QUE F est non vide FAIRE
u <- Extract( F )
E <- Union( E , u )
POUR tous les sommets v successeurs de u FAIRE
Relax(u,v,w)
FIN POUR
FIN TANT QUE
Ce que je fais :
* Création de l'ensemble E (qui contient mon sommet de départ) puis création de l'ensemble F (F est une file qui contient tous mes sommets (sauf le start), non trié car la distance de chacun vaut 1, je n'ai donc pas de "priorité").
* Je boucle tant que F n'est pas vide
* Je boucle sur la 2 ème dimensions de mon tableau (indice i)
* Je test si graph[u][i] == 1 (c'est que j'ai affaire a un point adjacent à u).
Mon problème ce situe ici, ma prochaine condition n'est jamais valider (relachement des arcs):
Si graph[u][i] > graph[u][u] + 1 alors grah[u][i] = graph[u][u] + 1.
Chez moi ca donne 0 ou 1 selon la case > 1, donc ces normal que je ne rentre jamais dans cette condition...
Il y a quelques chose que je ne comprend pas, quit sont pas logique dans ce que je fais, pourriez-vous me donner des pistes de reflexions s'il vous plait ?
