Implementer algo de Dijkstra

Version imprimable

27/12/2009, 19h12
colamaya

Implementer algo de Dijkstra

bonjour a tous et bonnes fetes de fin d'année,
j'ai un soucis avec l'algo de Dijkstra, je n'y arrive pas...
j'ai actuellement une classe Graphe (non orienté), Sommet et Aretes et je me dois de trouver le plus court chemin d"un point a un autre avec dijkstra. le graphe est en fait un maillage régulier en forme de rectangle, un peu comme un quadrillage.
pour l'instant je n'ai que initialiser : tous les sommets marqués à -1 (cad l'infini) et le sommet source à 0.
mais ensuite...
si vous pouviez m'aider, merci

ps : j'ai dja regardé sur le net (wiki,etc...)
28/12/2009, 11h42
Lavock

De mémoire, l'algo de dijkstra (imprononçable se nom ><) est super bourin -> il faut que tu parcours "tout" le graphe oO.

Qu'est-ce qui te bloque réellement dans cette algorithme ? En gros, le but c'est de faire un arbre de parcours. Après, je suis pas sûr, mais je crois qu'il vaut mieux le parcourir de manière horizontale si tu fais du Dijkstra pure.

Les optimisations principale sont => passage du parcours horizontale au parcours vertical "intelligent" ou semi-prévisioniste.

Passage d'un arbre en graphe -> évité de calculer des portion de parcours déjà vu dans d'autre parcours.

Mais surtout, au vue de la lourdeur de Dijkstra, es-tu sûr que c'est ce qu'il te faut ? Quelle sont tes domaine d'application ? Routage, jeu ?
28/12/2009, 13h02
colamaya

mon application c'est : appliquer dijkstra a ce graphe :)
mon probleme c'est que je n'arrive pas a l'implémenter...comment stocker les infos petit a petit
28/12/2009, 13h35
fabthegreat

Hola,

as-tu regardé:
http://www.nimbustier.net/publicatio...mentation.html

a+
28/12/2009, 17h01
koala01

Salut,

Citation:

Envoyé par Lavock

De mémoire, l'algo de dijkstra (imprononçable se nom ><)

on dirait quelqu'un qui éternue :P

Citation:

est super bourin -> il faut que tu parcours "tout" le graphe oO.

Non, pas forcément...

D'autant moins si les différentes arrêtes ne sont pas de taille égale (ce qui n'est, malheureusement, apparemment pas le cas du problème cité)
28/12/2009, 17h50
colamaya

oui j'ai vu, mais ca me parait un peu compliqué
ne peut on pas créer une simple fonction dijkstra prenant en argumant le poitn de départ et d'arrivée, et en ne travaillant qu'avec des listes ?
un peu comme ici : http://fr.wikipedia.org/wiki/Algorithme_de_Dijkstra ?
29/12/2009, 12h21
Lavock

Citation:

Envoyé par koala01

Non, pas forcément...

D'autant moins si les différentes arrêtes ne sont pas de taille égale (ce qui n'est, malheureusement, apparemment pas le cas du problème cité)

D'ou le tout entre guillemet => cela relève du pire des cas/ de ce qu'il faut chercher à faire.

[EDIT pour répondre un peu quand même] Comme je l'ai dit, l'idée et de stocker les parcours dans un arbre. A chaque noeud de l'arbre correspond les éventualité de chemin différent.

Chaque noeud à une valeur associé => le "temps" pour y arriver depuis le précédent noeud. Une nouvelle possibilité intervient ? Tu stockes la valeur temps dans ton noeud, tu reprend à 0 jusq'au prochain noeud. <= Cette description est un parcours en "profondeur" de l'arbre de parcours.
02/01/2010, 15h20
barmic

Citation:

Envoyé par colamaya

oui j'ai vu, mais ca me parait un peu compliqué
ne peut on pas créer une simple fonction dijkstra prenant en argumant le poitn de départ et d'arrivée, et en ne travaillant qu'avec des listes ?
un peu comme ici : http://fr.wikipedia.org/wiki/Algorithme_de_Dijkstra ?

Personnellement je l'ai implémenté en Java il y a peu et j'ai créé une classe qui prends dans le constructeur le graphe, puis une fonction qui me retournait toutes les distances (mon but était de trouver tout les noeuds qui était à une certaines distances). Avec les fonction initialisation et next en fonction privée de la classe.

Pour ce qui est de l'algorithme, l'article de Wikipedia est peut être pas hyper claire parce qu'il découpe l'algorithme, mais ce n'est pas si compliqué.

Je te conseille de d'abord essayer de simplement calculer la distance minimale de chaque noeud de ton graphe. C'est ce que fait l'algorithme de dijkstrat.

Une fois que tu arrive à faire ça. Il faudra adapter l'algorithme pour se souvenir du chemin.

La dernière étape seras d'optimiser l'ensemble parce que tu peut facilement te retrouver à consommer beaucoup de mémoire. Mais les structures de données vraiment optimisées pour Dijkstrat je te conseil de voir ça après coup.