RM50Man
Messages postés314Date d'inscriptionmercredi 1 novembre 2000StatutMembreDernière intervention20 août 2006
-
27 avril 2005 à 00:08
RM50Man
Messages postés314Date d'inscriptionmercredi 1 novembre 2000StatutMembreDernière intervention20 août 2006
-
28 avril 2005 à 15:34
Est - ce que quelqu'un pourrait comment trouver la matrice ligne
ds l algorithme de dijkstra!!!!
Merci!!!
sphaxslayer
Messages postés216Date d'inscriptionmardi 5 avril 2005StatutMembreDernière intervention17 septembre 2008 28 avril 2005 à 12:28
:|
euh nan ... lol
pas tant que ca...
si c'est pour le plaisir que t'as voulu t'farcir Dijkstra pour ensuite le programmer PAR PLAISIR ouais...C'est chiant...lol...mais j'en doute...:p
Parce que l'algo il se trouve partout partout partout...apres coder l'algo c là la difficulté mias t'as pas tout à t'taper dans l'analyse et l'algorithmie :)
fin c'est sur que y'aura des truc chiants...mais t'as un bon bout qu'est fait quoi
"Un seul Être vous manque, et tout est dépeuplé..."
sphaxslayer
Messages postés216Date d'inscriptionmardi 5 avril 2005StatutMembreDernière intervention17 septembre 2008 28 avril 2005 à 12:46
tiens va voir ça, c'est simple...apres à toi d'coder :) mais
"si tout était déjà fait et que rien n'était à faire, alors que ferions-nous?"(moi )http://langevin.univ-tln.fr/CDE/PL1/tp6.html
"Un seul Être vous manque, et tout est dépeuplé..."
RM50Man
Messages postés314Date d'inscriptionmercredi 1 novembre 2000StatutMembreDernière intervention20 août 2006 28 avril 2005 à 13:33
C koi la fonction de pondération!!
et l initialisation c moi ki doit entrer la valeur des distances!!
et x et y les variables des sommets , c leur abscisse et ordonnee!!!
RM50man
Vous n’avez pas trouvé la réponse que vous recherchez ?
sphaxslayer
Messages postés216Date d'inscriptionmardi 5 avril 2005StatutMembreDernière intervention17 septembre 2008 28 avril 2005 à 13:44
la fonction de pondération c'est juste la fonction qui met les cout sur les aretes...qui "pondère" les chemins quoi...pour l'initialisation oui, j'pense qu'il faudrait que tu fasse une sorte de tableau par exemple avec les indices correspondant aux aretes: du genre ind 0 <=> arete de A à B, ind 1 <=> arete de B à C etc....et pour x et y, c'est les 2 sommets que tu regardes: tu prends x est le plus pres du sommet source etc etc...mais au pire si cet algo est pas assez détaillé fouille sur google algorithme Dijkstra tu vas en trouver plusieurs, y'en a ptete qui s'ront mieux expliqués moi j'avais pris le premier venu paske y'avait l'algo :)
sta besoin, j't'aide encore ;)
"Un seul Être vous manque, et tout est dépeuplé..."
sphaxslayer
Messages postés216Date d'inscriptionmardi 5 avril 2005StatutMembreDernière intervention17 septembre 2008 28 avril 2005 à 14:21
euh un tas...? qu'esseucé? lol euh j'utlises rien moi lol...si tu parles pour le tableau c'était qu'une idée comme ça à l'impro, y'a p'tete une meilleure solution...
"Un seul Être vous manque, et tout est dépeuplé..."
sphaxslayer
Messages postés216Date d'inscriptionmardi 5 avril 2005StatutMembreDernière intervention17 septembre 2008 28 avril 2005 à 14:39
euh bah je sais pas...p'tete avec un arbre binaire c'est faisable, mais ils mettent quoi dans leur arbre...? le x et le y? et en fait il regarde si de S le plus court c'est x1 ou y1, apres dans la branche ils continuent , par exemple pour x1, le plus court c'est x1.2 ou x1.2 etc ...? ca doit etre ca le principe nan ?
S
/ \
x1 y1
/ \ / \
x1.1 x1.2 y1.1 y1.2
etc ...
(sachant que S est la source, on est bien d'accord...et tu prends les branches qui coutent moins cher genre sur l'dessin d'art que j'ai fait tu t'imagines que les x et les y ce sont les sommets et que chaque trait est pondéré par le cout du lien...)
"Un seul Être vous manque, et tout est dépeuplé..."
RM50Man
Messages postés314Date d'inscriptionmercredi 1 novembre 2000StatutMembreDernière intervention20 août 2006 28 avril 2005 à 14:49
L'algorithme de Dijkstra pourra mis en œuvre efficacement en stockant le graphe sous forme de listes adjacentes et en utilisant un tas comme une file à priorités pour réaliser la fonction <TT>Trouve_min</TT>. Si le graphe possède m arcs et n nœuds, alors la complexité de l'algorithme est (en supposant que les comparaisons des poids d'arcs soient à temps constant) :
sphaxslayer
Messages postés216Date d'inscriptionmardi 5 avril 2005StatutMembreDernière intervention17 septembre 2008 28 avril 2005 à 14:52
alors là.......si toi tu comprends, c'est ton tour de m'expliquer :p parce que moi j'ai appris comme j't'ai expliqué Dijkstra et euh..bah là j'pige rien et à mon avis c'est plus haut que mes études...(j'ai qu'un DUT info moi...) ceci dit le coup des listes triées c pas bete, c'est comme un arbre finalement ou a chaque fois ta les branches c les chemins les plus courts...etc etc mais bon j'pense que ca m'dépasse amplement la
"Un seul Être vous manque, et tout est dépeuplé..."
RM50Man
Messages postés314Date d'inscriptionmercredi 1 novembre 2000StatutMembreDernière intervention20 août 2006 28 avril 2005 à 15:20
Le site ou je suis i disent que tu stockes les sommets selectionner ds un tableau predecesseur,
ce tableau va donc stocker tous les sommets ki font partie du plus court chemin
Mais si par ex, pour aller de sdeb a sfin, tu stockes tous les sommets selectionnés,
y aura aussi les sommets ki vont pas a sfin, puisque l algo de dijkstra trouve le chemin le plus court vers ts les sommets !!!!!