trouver le plus court chemin dans un graphe

**buggen25** · 14/08/2008, 15h04

Bonjour tout le monde :
j'ai un petit problème qui me tracasse, je voudrais implémenter un programme qui me permetterai de trouver le chemin le plus court dans un graphe, j'ai trpouvé un solution qui consiste a utiliser l'algorithme de Dijkstra ( encore et toujours )..dont le pseudo code si je m'en souvien tres bien et comme ceci

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
 
struct Noeud
  queue<arc> arcs;// les arcs qui sortent du noeud
  valeur poids;// la valeurs du noeud
  Noeud pred;// le predecesseurs (parent)
 
struct arc
  valeur poids;//
  Noeud Depart;
  Noeud Arrivée;
 
Initialiser le noeud de depart a zero
mettre les autres neuds a l'infini
pour tout les noeuds d'une liste selectionner le noeud de poids faible 
pour tout les arcs sortant du noeud courrant (arccourrant)
si( arccourrant.Arrivée.poids > arccourrant.poids + arccourrant.Depart.poids )
alors
   arccourrant.Arrivée.poids=arccourrant.poids + arccourrant.Depart.poids
      stack.push_back(); // retirer le la pile

merci pour votre aide

Scorpi0 · 14/08/2008, 15h14

Bonjour,

Je n'ai pas bien saisi ou se situait le problème.

**buggen25** · 14/08/2008, 15h43

merci pour ta brève réponse;
je voudrai savoir si t'a une idée sur cet algorithme, la théorie est simple, mais je pense que tu connais la différence entre la théorie et la pratique
comment faire pour coder l'algorithme de dijkstra

Scorpi0 · 14/08/2008, 15h47

Wikipedia

Edit : Si tu as une question précise sur l'algorithme, un point que tu ne comprend pas, n'hésite pas à demander. Mais vouloir tout qu'on t'expliques alors qu'il existe plus de ressources sur google que tu ne pourras en lire, c'est un peu abusé.