Discussion :

[line86]

Bonsoir,
Je cherche a coder Dijkstra en C, j'ai donc regardé l'algo sur Wikipedia et j'aurais besoin d'explications dessus.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
 
Dijkstra(G,Poids,sdeb)
 Initialisation(G,sdeb)
 P := ensemble vide
 Q := ensemble de tous les nœuds
 tant que Q n'est pas un ensemble vide
       faire s1 := Trouve_min(Q) (1)
          P := P union {s1} (2)
          pour chaque nœud  s2 voisin de s1
              faire maj_distances(s1,s2)

(1) - On doit trouver la valeur min contenu dans la matrice qui represente le graphe? A quoi correspond S1?
(2) - A quoi correspond union?

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
Initialisation(G,sdeb)
1 pour chaque point s de G
2    faire d[s] := infini             /* on initialise les sommets autres que sdeb à 0 */[3]
3       prédecesseur[s] := 0          /* car on ne connaît au départ aucun chemin entre s et sdeb */
4 d[sdeb] := 0                        /* sdeb étant le point le plus proche de sdeb */

Comment coder infini? par -1 ca va poser des difficultées quand on va vouloir faire une addition ou autre non?

Merci pour votre aide

[Jedai]

(1) - On doit trouver la valeur min contenu dans la matrice qui represente le graphe? A quoi correspond S1?

La définition de Trouve_min est dans l'article Wikipédia. s1 est bien sûr le sommet de Q qui est le plus proche de sdeb.

(2) - A quoi correspond union?

A l'union ensembliste, quoi d'autre ?

Comment coder infini? par -1 ca va poser des difficultées quand on va vouloir faire une addition ou autre non?

Si tu le codes par -1 il faudra faire attention dans la maj_distances et dans Trouve_min à traiter -1 spécialement, une alternative est de mettre le plus grand nombre possible selon le type choisi pour la distance. Note que float et double ont normalement une valeur +Inf selon la norme IEEE.

--
Jedaï