Discussion :

[sbill]

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 :

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 ?

[CliffeCSTL]

Attention avec les notations :

d[v], d[u]
w(u, v)
graph[u][v]

regarde bien ce que tu as écrit.

[sbill]

Effectivement, je m'en suis rendu compte dans la journée

Ca fonctionne mieux maintenant.
J'ai une petite question concernant F <- tous les sommets de G, généralement une file de priorité est utiliser cependant comment savoir à l'avance les sommets qui seront utiliser et donc les positionner en début de File afin de ne pas tous parcourir lors de la recherche du poids minimal ?

Merci.