Discussion :

[newtito]

je dois trouver le plus court chemin de mon graphe avec un algorithme de parcours en largeur qui etudie les possiblités en totalité (et pas avec dijkstra etc...). J' ai l' algo de parcours facile mais je n'arrive pas a voir comment memoriser la route a prendre. et si je dois les memoriser toutes comment faire ?

merci beaucoup les gars!

[PRomu@ld]

Une idée toute bête : mémoriser dans une file (une liste ou un tableau font très bien l'affaire) le chemin parcouru pour atteindre un sommet donné, une fois que tu atteinds un sommet, tu lui enregistres ce chemin.

Si ton algo est récursif, c'est d'autant plus simple.

Mais attention cependant, le parcours en largeur te permet de calculer un plus court chemin dans deux sens :

- soit les arêtes de ton graphe sont pondérés du coëficient 1, dans ce cas tu auras le même résultat que dijkstra.
- soit les arêtes ont une pondération quelconque et dans ce cas, ton plus court chemin ne sera que le plus court chemin dans le sens où ce sera le chemin qui minimise le nombre de sommet visité et non plus celui qui minimise le poids de ce chemin.

[Graffito]

Bonjour,

Regarde parmi les post précédents "A étoile [A*, Astar]".
Il traite du même sujet.

[newtito]

je suis d'accoerd il faut enregistrer ce chemin, mais comment faire, c'est ca mon probleme? voici l'algo de parcours en largeur de mon graphe (en gros):

n<-noeudSource
enfile(n);
tant que file_non_vide
n1<-defile()
marque(n1)
Pour tout successeur de n1 && nonMarque
enfile(succ)
fin tant que

voici mon algo de largeur, mais je n'arrive pas a integrer une liste ou des listes qui me donneraient les villes intermediares entre mon noeud initial et mon noeud d'arrivée, une fois que je suis arrivé a mon but .
Car cette algo parcours tout le graphe en largeur , et je ne peux pas savoir par quelle 'route' en avance il va arriver, donc je dois toutes les memorisés je pense, et meme ca je voie pas comment faire car ca reviendrait a créer de nombreuses listes ?

[Graffito]

Bonjour,

Supposons que l'on ait un graphe qui permette de connaitre les liens de chaque noeud (noeuds contigus) et la distances correspondante.

Pour trouver le plus court chemin d'un noeud A à un noeud B, on calculera calculera le plus court chemin du noeud A à tous les noeuds du graphe.

On a besoin comme de définir pour chaque noeud du graphe les valeurs suivantes :
- DA(X) : distance d'un noeud X à A (que l'on initialisera à "infinie").
- PR(X) : prédecesseur de X sur le chemin B à A.

ProcessNode est la procédure permettant de traiter tous les noeuds contigus d'un noeud X.

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
Code: 
Procedure ProcessNode(X) ; 
begin 
Pour i de 1 au nombre de noeuds contigus à X : 
   begin 
   Y=noeud_contigu(X,i) 
   distance_ Y_ à_ A_via_X = DA(X) + Dist(X,Y) 
   si distance_ Y_ à_ A_via_X < DA(Y) : 
       begin 
       DA(Y) = distance_ Y_ à_ A_via_X 
       PR(Y) = X 
       si Y différent de B : ProcessNode(Y) 
       end 
   end 
end

On fait ProcessNode(A) et, au retour, on a la distance dans DA(B) et on récupére le chemin en parcourant les prédecesseurs de B jusqu'à A.
Evidement, Si DA(B)="infinie", il n'y a pas de chemin de A à B.

Pour optimiser dans une application réélle, on peut modifier l'ordre de parcours des noeuds contigus en utilisant des informations "géographiques" afin de traiter la ligne droite AB en priorité. On a alors des chances de tomber assez vite sur le point B. On peut alors comparer, dans la procedure processNode, DA(X) à DA(B) et si DA(X)>DA(B)+Distance_à_vol_d'oiseau(X,B), il est alors inutile de traiter le noeud X.

[newtito]

salut graffito,

je crois comprendre ce que tu veux dire mais ca sort du cadre du parcours en largeur et de la recherche aveugle ou brute, je dois tous parcourir et n'utiliser que cet algo.
En tout cas merci pour tes reponses chef !