Dijkstra: le chemin le plus court

Soyez le premier à donner votre avis sur cette source.

Vue 17 249 fois - Téléchargée 1 885 fois

Description

Comme le dit le titre, ce prog utilise l'algo de dijkstra pour trouver le plus court chemin dans une map (voir screenshot). Utilité? donner une solution simple à un prob récurrent, celui des trajets... quels chemins prendre pour aller à un endroit le plus rapidement possible? c'est aussi le problème d'internet et des transferts de données dans le monde entier... Il faut dans tous les cas emprunter le chemin le moins couteux, le plus rapide. Comment faire? solution bourin, simuler tous les trajets possibles et regarder lequel est le plus rapide. Mais sachez que pour un graph de 18 sommets (c'est à dire 18 noeuds) il existe 18! chemins... soit 6 402 373 705 728 000 chemins, et avec un ordi qui fait 1 milliard de calculs (on va dire 1chemin=1calcul) à la seconde, il lui faudrait 75 jours pour les faire tous...lol ma map a ~70 sommets... il faut donc utliser une autre technique, et parmi celles là il y a l'algo de dijkstra: principe de sous-optimalité & co (pour plus d'info, tapez dijkstra sur le net), qui trouve beaucoup (beaucoup lol) plus rapidement le chemin... voilà, si ya des comments n'hésitez pas (dur de se mettre au .net :)
antislash

rem: le code comme il est ne permet que de sélectionner des intersections ou des angles... si vous voulez pouvoir placer n'importe où votre point d'arrivée ou de départ, il suffit de mettre quelques lignes précisez en comment... voilà!

Codes Sources

A voir également

Ajouter un commentaire Commentaires
cs_Bidou Messages postés 5487 Date d'inscription dimanche 4 août 2002 Statut Membre Dernière intervention 20 juin 2013 60
27 janv. 2007 à 09:21
Dargos> Mieux vaut tard que jamais, voici une source sur A* sur C#
http://www.csharpfr.com/codes/ALGORITHME-PATHFINDING-ASTAR_41235.aspx
tems Messages postés 2 Date d'inscription lundi 21 août 2000 Statut Membre Dernière intervention 25 novembre 2006
25 nov. 2006 à 01:21
Excellent algorithme.

Je souhaiterais ajouter des points de passages obligés. Quelqu'un pourrait-il m'aiguiller ?

Merci d'avance.

Tems
cs_Dargos Messages postés 13 Date d'inscription mardi 18 avril 2006 Statut Membre Dernière intervention 27 mars 2008
18 avril 2006 à 11:10
arf, du vb...
comment avoir la meme chose en c# svp !
cuq Messages postés 345 Date d'inscription mardi 3 juin 2003 Statut Membre Dernière intervention 21 mars 2008 2
12 sept. 2005 à 17:57
Pour le problème de passage à VB6 voir la source :
http://www.vbfrance.com/code.aspx?ID=25097
Sur le même site avec l'algorythme Dijkstra et A* ce qui permet de compararer les deux méthodes.Pour ta source AntiSlash ben désolé j'ai pas VB.net donc je ne peux pas tester c'est bien domage.
cs_AntiSlash Messages postés 61 Date d'inscription dimanche 21 juillet 2002 Statut Membre Dernière intervention 23 avril 2003
8 mai 2003 à 21:24
Merci pour les comments et la note, ca fait tj plaisir!
Shivan: en effet, c pas moi qui ai pondu l'algo, sinon il s'appelerait pas Dijkstra! :)
Dino: comme l'a dit shivan, sur cette source ya pratiquement rien a changer pour la passer en vb6...
@+
Afficher les 12 commentaires

Vous n'êtes pas encore membre ?

inscrivez-vous, c'est gratuit et ça prend moins d'une minute !

Les membres obtiennent plus de réponses que les utilisateurs anonymes.

Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.

Le fait d'être membre vous permet d'avoir des options supplémentaires.