Pages : 1
#1 Le 22/04/2007, à 22:06
- xcxl
Algorithme de Dijkstra
Bonjour, j'ai fait quelque recherche à propos de l'algorithme de Dijkstra (EDIT : qui permet de trouver le chemin le plus rapide entre 2 points)et je n'ai pas réussi à trouver une seule explication claire (je suis en 2nd générale). Quelqu'un peut-il me dire ce que signifie "le poid des arrêtes" ou alors me donné un joli site avec plein de shéma.
Merci
Je vais prendre quelques aspirines...
Dernière modification par xcxl (Le 22/04/2007, à 22:16)
Hors ligne
#2 Le 22/04/2007, à 22:16
- hector
Re : Algorithme de Dijkstra
un graphe est composé de sommets et d'arêtes. Si il est pondéré , on attribue à chaque arête un poids.
si tu prends comme exemple de graphe le réseau de la RATP, 2 stations adjacentes sont reliées par une arête , qu'on peut pondérer par un temps (le temps mis pour aller d'une station à l'autre)
l'algorithme de djisktra permet de trouver une solution optimale pour aller d'une station A à une station B.
pour son fonctionnement proprement dit, pas facile d'expliquer comme ça, surtout que je suis en correspondance! (station C)
Bon courage.
Dernière modification par hector (Le 22/04/2007, à 22:18)
Hors ligne
#3 Le 22/04/2007, à 22:19
- xcxl
Re : Algorithme de Dijkstra
Pondéré c'est quand on il y a des points que l'on peut relier?
Hors ligne
#4 Le 22/04/2007, à 22:22
- hector
Re : Algorithme de Dijkstra
non c'est un coefficient (appelé poids) que tu attribues à chaque arête (une arête c'est ce qui relie 2 sommets)
salut
Hors ligne
#5 Le 23/04/2007, à 00:00
- Zoolonly
Re : Algorithme de Dijkstra
Je ne sais pas vraiment pourquoi tu as besoin de dikjstra, mais ce poly peux t'aider :
http://bigbozoid.free.fr/CoursLICENCE3/ … raphes.pdf
Hors ligne
#6 Le 23/04/2007, à 12:44
- xcxl
Re : Algorithme de Dijkstra
Merci c'est ce que je cherchai. Si j'ai besoin d'aide je vous dis. Merci pour le polycop.
Hors ligne
#7 Le 24/04/2007, à 21:45
- udo
Re : Algorithme de Dijkstra
Salut,
désolés pour le retard, j'avais fait un tipe dessus en sup donc je te poste l'adresse si ça peut t'aider:
http://kysicurl.free.fr/tipe/tipe.pdf
@+
#8 Le 01/05/2007, à 14:40
- xcxl
Re : Algorithme de Dijkstra
Cets encore mieux merci bcp
Hors ligne
Pages : 1