trouver le plus court chemin dans un graphe
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:
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
