Algorithme de dijkstra
RM50Man
Messages postés
314
Date d'inscription
mercredi 1 novembre 2000
Statut
Membre
Dernière intervention
20 août 2006
-
27 avril 2005 à 00:08
RM50Man Messages postés 314 Date d'inscription mercredi 1 novembre 2000 Statut Membre Dernière intervention 20 août 2006 - 28 avril 2005 à 15:34
RM50Man Messages postés 314 Date d'inscription mercredi 1 novembre 2000 Statut Membre Dernière intervention 20 août 2006 - 28 avril 2005 à 15:34
A voir également:
- Dijkstra c#
- C# dijkstra - Meilleures réponses
- Shortest path algorithm c# - Meilleures réponses
- Implémentation dijkstra sur macro excel vba ✓ - Forum Visual Basic 6
- Tri par comptage et tri de dijkstra. urgent!!! et au secours!!! - Forum C / C++ / C++.NET
36 réponses
sphaxslayer
Messages postés
216
Date d'inscription
mardi 5 avril 2005
Statut
Membre
Dernière intervention
17 septembre 2008
27 avril 2005 à 13:15
27 avril 2005 à 13:15
euh...je comprends pas très bien ton post, mais j'ai étudié Dijkstra peut-être que je pourrais t'aider si tu essayais d'être plus clair :s désolé...mais j'comprends pas ce que tu veux en fait
"Un seul Être vous manque, et tout est dépeuplé..."
"Un seul Être vous manque, et tout est dépeuplé..."
RM50Man
Messages postés
314
Date d'inscription
mercredi 1 novembre 2000
Statut
Membre
Dernière intervention
20 août 2006
27 avril 2005 à 13:24
27 avril 2005 à 13:24
Tu peux m'expliquer de A à Z , détaillé très clairement l ' algorithme de
dijkstra ??????
Par ce que g trouver sur internet c un peu du chinois!!!
RM50man
dijkstra ??????
Par ce que g trouver sur internet c un peu du chinois!!!
RM50man
sphaxslayer
Messages postés
216
Date d'inscription
mardi 5 avril 2005
Statut
Membre
Dernière intervention
17 septembre 2008
27 avril 2005 à 13:51
27 avril 2005 à 13:51
euh mouais...lol bon alors déjà tu veux que j't'explique pour du réseau ou pour des maths...? (c'est quasiment pareil, seulement pour des exemples ce sera plus concret je pense...) en tous les cas ce serait bien que tu me files ton adresse email en pv: je vais scanner mes cours et je te les enverrais, moi j'ai bien compris avec ces cours...et si t'as besoin de quelques explications en plus y'a pas de souci :) voili voilou...
par contre faudra atetndre un peu parce que la j'suis au boulot, et faut que je branche mon scanner ce soir en rentrant etc...donc ce sera peut-être demain dans la journée je ne sais pas...voilà!
en attendant va voir ce lien http://wims.unice.fr/wims/wims.cgi?session=2R22DBB94B.4&lang=fr&cmd=new&n=5&bound=1&module=U1%2Fgraph%2Fdijkstra.fr' target='_blank'>http://http://wims.unice.fr/wims/wims.cgi?session=2R22DBB94B.4&lang=fr&cmd=new&n=5&bound=1&module=U1%2Fgraph%2Fdijkstra.fr
c'est des exos pas mal...ds celui-ci tu pars du sommet A, et t uveux aller vers les autres: le truc c'est que t'as un ensemble de départ appelé S. dans ce S tu mets un sommet peu importe lequel, et tu dois trouver le plus court chemin de A vers tous les sommets (parce qu'ici on commence de A...) MAIS ces chemins ne doivent passer QUE par les sommets présents dans S...ensuite à la ligne suivante, tu ajoutes le sommets pour lequel la valeur était la plus petite dans le tableau
exemple: si t'as un tableau comme ca (on va de A vers les autres...)
S sommets A B C D E F
{ } - - - - - -
{A} 0 xi yi zi li di (disons ici que xi < {yi,zi,li,di} )
{A,B} . . . . . . . . . . . . . . . . . . . . .
Remarque: en cas d'égalité des valeurs, t'en prends une peu importe et à la ligne d'apres, tu devras prendre l'autre valeur qui était égale et non celle que t'as trouvé dans la ligne que tu viens de faire (cette derniere sera celle prise une fois que toutes les valeurs égales auront été traitées)
par exemple, si xi était égal à yi, tu aurais pu mettre C dans S, à condition qu'apres à la 4eme ligne, tu aies pris B à inclure dans S MEME si dans la ligne avec S={A,C} tu avais trouvé une valeur encore plus petite que xi...
bon voila c'est pas super clair mais avec le site pour visualiser tu devrais y arriver d'ici à ce que j'trouve mes cours :) si t'as besoin d'explications demande :)
"Un seul Être vous manque, et tout est dépeuplé..."
par contre faudra atetndre un peu parce que la j'suis au boulot, et faut que je branche mon scanner ce soir en rentrant etc...donc ce sera peut-être demain dans la journée je ne sais pas...voilà!
en attendant va voir ce lien http://wims.unice.fr/wims/wims.cgi?session=2R22DBB94B.4&lang=fr&cmd=new&n=5&bound=1&module=U1%2Fgraph%2Fdijkstra.fr' target='_blank'>http://http://wims.unice.fr/wims/wims.cgi?session=2R22DBB94B.4&lang=fr&cmd=new&n=5&bound=1&module=U1%2Fgraph%2Fdijkstra.fr
c'est des exos pas mal...ds celui-ci tu pars du sommet A, et t uveux aller vers les autres: le truc c'est que t'as un ensemble de départ appelé S. dans ce S tu mets un sommet peu importe lequel, et tu dois trouver le plus court chemin de A vers tous les sommets (parce qu'ici on commence de A...) MAIS ces chemins ne doivent passer QUE par les sommets présents dans S...ensuite à la ligne suivante, tu ajoutes le sommets pour lequel la valeur était la plus petite dans le tableau
exemple: si t'as un tableau comme ca (on va de A vers les autres...)
S sommets A B C D E F
{ } - - - - - -
{A} 0 xi yi zi li di (disons ici que xi < {yi,zi,li,di} )
{A,B} . . . . . . . . . . . . . . . . . . . . .
Remarque: en cas d'égalité des valeurs, t'en prends une peu importe et à la ligne d'apres, tu devras prendre l'autre valeur qui était égale et non celle que t'as trouvé dans la ligne que tu viens de faire (cette derniere sera celle prise une fois que toutes les valeurs égales auront été traitées)
par exemple, si xi était égal à yi, tu aurais pu mettre C dans S, à condition qu'apres à la 4eme ligne, tu aies pris B à inclure dans S MEME si dans la ligne avec S={A,C} tu avais trouvé une valeur encore plus petite que xi...
bon voila c'est pas super clair mais avec le site pour visualiser tu devrais y arriver d'ici à ce que j'trouve mes cours :) si t'as besoin d'explications demande :)
"Un seul Être vous manque, et tout est dépeuplé..."
RM50Man
Messages postés
314
Date d'inscription
mercredi 1 novembre 2000
Statut
Membre
Dernière intervention
20 août 2006
27 avril 2005 à 14:46
27 avril 2005 à 14:46
Mon adresse e_mail , c'est RM50man@msn.com
Merci!!!!
RM50man
Merci!!!!
RM50man
Vous n’avez pas trouvé la réponse que vous recherchez ?
Posez votre question
sphaxslayer
Messages postés
216
Date d'inscription
mardi 5 avril 2005
Statut
Membre
Dernière intervention
17 septembre 2008
27 avril 2005 à 14:57
27 avril 2005 à 14:57
ok, mais essaye de piger le truc avec ce que j't'ai envoyer, c'est pas tres dur en fait...le graphe c pour t'indiquer les chemins, et la matrice c'est les couts de chaque lien: en fait ca se lit comme ca:
MATRICE:
A B C D
A 0 5 inf 1 Pour ALLER de A VERS A= 0, B=5, C=infini (dc pas possible), D=1
B 1 0 4 inf Pour ALLER de B VERS A =1, B=0, C=4, D=infini (*)
C ... ...
D
et donc dans ton tableau tu dis que tu pars de A, en passant que par les somments de S pour rejoindre les autres sommets, et si par exemple A->C n'existe pas, mais que A->B oui, et que B->C existe, alors une fois que t'auras A et B dans S, tu pourras dire que A->C = A->B + B->C (ca fait un peu penser à la relation de Chasles :) )
(*) par exemple là, à cette étape, le plus court chemin de A vers D c'est 1 car A va vers D directement avec un cout de 1...Par contre, le plus court de A vers C, c'est 5+4=9 car A va vers B avec un cout de 5 et B va vers C avec un cout de 4...avec les données que j'ai mises dans la matrice, c'est le plus court, maintenant si apres avec la ligne de C ou de D t'en trouves un plus court que 9, tu prends... :)
essaie de piger avec ce que j't'ai donné et le site (conseil: mets des niveaux simples pour commencer sur le site...)
"Un seul Être vous manque, et tout est dépeuplé..."
MATRICE:
A B C D
A 0 5 inf 1 Pour ALLER de A VERS A= 0, B=5, C=infini (dc pas possible), D=1
B 1 0 4 inf Pour ALLER de B VERS A =1, B=0, C=4, D=infini (*)
C ... ...
D
et donc dans ton tableau tu dis que tu pars de A, en passant que par les somments de S pour rejoindre les autres sommets, et si par exemple A->C n'existe pas, mais que A->B oui, et que B->C existe, alors une fois que t'auras A et B dans S, tu pourras dire que A->C = A->B + B->C (ca fait un peu penser à la relation de Chasles :) )
(*) par exemple là, à cette étape, le plus court chemin de A vers D c'est 1 car A va vers D directement avec un cout de 1...Par contre, le plus court de A vers C, c'est 5+4=9 car A va vers B avec un cout de 5 et B va vers C avec un cout de 4...avec les données que j'ai mises dans la matrice, c'est le plus court, maintenant si apres avec la ligne de C ou de D t'en trouves un plus court que 9, tu prends... :)
essaie de piger avec ce que j't'ai donné et le site (conseil: mets des niveaux simples pour commencer sur le site...)
"Un seul Être vous manque, et tout est dépeuplé..."
sphaxslayer
Messages postés
216
Date d'inscription
mardi 5 avril 2005
Statut
Membre
Dernière intervention
17 septembre 2008
27 avril 2005 à 15:01
27 avril 2005 à 15:01
en fait j'viens de voir que le lien marchait pas super...prends celui-ci et mets un niveau bas :)
http://wims.unice.fr/wims/fr_U1~graph~dijkstra.fr.html
"Un seul Être vous manque, et tout est dépeuplé..."
http://wims.unice.fr/wims/fr_U1~graph~dijkstra.fr.html
"Un seul Être vous manque, et tout est dépeuplé..."
RM50Man
Messages postés
314
Date d'inscription
mercredi 1 novembre 2000
Statut
Membre
Dernière intervention
20 août 2006
27 avril 2005 à 15:09
27 avril 2005 à 15:09
Tu ma envoyé quelque choses?????
RM50man
RM50man
sphaxslayer
Messages postés
216
Date d'inscription
mardi 5 avril 2005
Statut
Membre
Dernière intervention
17 septembre 2008
27 avril 2005 à 15:13
27 avril 2005 à 15:13
nan j'parlais du forum...là j'suis pas chez moi donc mes cours j'les ai pas, et une fois chez moi faut que je les retrouve......c'est question de simplifier, sinon j'peux t'expliquer par forum mais ce sera un peu plus long quoi...mais là normalement si t'as commencé ce que j't'ai filé dans le forum, + le site pour t'exercer, tu devrais commencer à piger des trucs nan? ou au moins à avoir des questions ? :D
"Un seul Être vous manque, et tout est dépeuplé..."
"Un seul Être vous manque, et tout est dépeuplé..."
RM50Man
Messages postés
314
Date d'inscription
mercredi 1 novembre 2000
Statut
Membre
Dernière intervention
20 août 2006
27 avril 2005 à 15:17
27 avril 2005 à 15:17
C'est la matrice ligne qu'y faut trouver que je comprends pas ds l exo!!!
RM50man
RM50man
RM50Man
Messages postés
314
Date d'inscription
mercredi 1 novembre 2000
Statut
Membre
Dernière intervention
20 août 2006
27 avril 2005 à 15:19
27 avril 2005 à 15:19
En continuant l'algorithme, vous auriez trouvé la matrice ligne
<CENTER></CENTER>Le détail des étapes est :
Ensemble S |
F(A) |
F(B) |
F(C) |
F(D) |
F(E) |
----
{A},
0,
,
,
,
,
----
{A,B},
0,
,
,
,
,
----
{A,B,C},
0,
,
,
,
,
----
{A,B,C,D},
0,
,
,
,
,
----
{A,B,C,D,E},
0,
,
,
,
tu pe m expliquer ca!!!ca a l air facile!!
RM50man
<CENTER></CENTER>Le détail des étapes est :
Ensemble S |
F(A) |
F(B) |
F(C) |
F(D) |
F(E) |
----
{A},
0,
,
,
,
,
----
{A,B},
0,
,
,
,
,
----
{A,B,C},
0,
,
,
,
,
----
{A,B,C,D},
0,
,
,
,
,
----
{A,B,C,D,E},
0,
,
,
,
tu pe m expliquer ca!!!ca a l air facile!!
RM50man
sphaxslayer
Messages postés
216
Date d'inscription
mardi 5 avril 2005
Statut
Membre
Dernière intervention
17 septembre 2008
27 avril 2005 à 15:21
27 avril 2005 à 15:21
ben ta matrice ligne, c'est la ligne avec les plus courts chemins...
par exemple:
F = (0, 4 , 5, 2, 10, 3)
ca veut dire que de A vers A le plus court c 0
de A vers B c 4
de A vers C c 5 etc etc...
et cette fonction, bah c la derniere ligne du tableau, quand t'as tous les sommets dans S...et donc les plus courts chemins vers tous les sommets
:)
"Un seul Être vous manque, et tout est dépeuplé..."
par exemple:
F = (0, 4 , 5, 2, 10, 3)
ca veut dire que de A vers A le plus court c 0
de A vers B c 4
de A vers C c 5 etc etc...
et cette fonction, bah c la derniere ligne du tableau, quand t'as tous les sommets dans S...et donc les plus courts chemins vers tous les sommets
:)
"Un seul Être vous manque, et tout est dépeuplé..."
sphaxslayer
Messages postés
216
Date d'inscription
mardi 5 avril 2005
Statut
Membre
Dernière intervention
17 septembre 2008
27 avril 2005 à 15:30
27 avril 2005 à 15:30
bah la ds ton exemple, ca veut dire que y'a aucune liaison vers les sommets: de A vers n'importe lequel autre, c'est infini donc le lien est soit de cout infini soit inexistant, c pareil...et pareil pour les autres: en fait ton graphe ressemble à des sommets sans liens :)
"Un seul Être vous manque, et tout est dépeuplé..."
"Un seul Être vous manque, et tout est dépeuplé..."
RM50Man
Messages postés
314
Date d'inscription
mercredi 1 novembre 2000
Statut
Membre
Dernière intervention
20 août 2006
27 avril 2005 à 15:37
27 avril 2005 à 15:37
chui un ane je crois!!!!
RM50man
RM50man
RM50Man
Messages postés
314
Date d'inscription
mercredi 1 novembre 2000
Statut
Membre
Dernière intervention
20 août 2006
27 avril 2005 à 15:42
27 avril 2005 à 15:42
Non je rigole , j'ai enfin compris, c'était un bug de cerveau!!!!
Tu mas bien aidé qd meme
Merci!!!
Mais tu pe qd meme m envoyer tes cours !!!!
RM50man
Tu mas bien aidé qd meme
Merci!!!
Mais tu pe qd meme m envoyer tes cours !!!!
RM50man
sphaxslayer
Messages postés
216
Date d'inscription
mardi 5 avril 2005
Statut
Membre
Dernière intervention
17 septembre 2008
27 avril 2005 à 15:49
27 avril 2005 à 15:49
lol non t'inquietes..au départ c chiant surtout sur forum ou on peut pas dessiner :s
essaye de te faire un graphe avec 4 pauvres sommets, tu mets des pondérations sur tes liens, et apres tu trace ton tableau: dans ce tableau fait pas come le site fait plutot
S R A B C D
{} {A,B,C,D} - - - -
où R= ce qui n'est pas dans S...genre à l'initialisation ton R contient TOUS les sommets et au fur et a mesure que tu e najoute un dans S tu l'enleve de R... déjà ca t'marque ceux que tu peux prendr et ceuq ue tu peu pas prendre, ensuite faut toujours raisonner avec cette phrase:
"je pars de A vers...." et de là, tu regrde le plus court: en pensant bien que tu peux parfois passer par plusieurs sommets et ce sera plus court qu'en direct...ca dépend des pondération des liens...
"Un seul Être vous manque, et tout est dépeuplé..."
essaye de te faire un graphe avec 4 pauvres sommets, tu mets des pondérations sur tes liens, et apres tu trace ton tableau: dans ce tableau fait pas come le site fait plutot
S R A B C D
{} {A,B,C,D} - - - -
où R= ce qui n'est pas dans S...genre à l'initialisation ton R contient TOUS les sommets et au fur et a mesure que tu e najoute un dans S tu l'enleve de R... déjà ca t'marque ceux que tu peux prendr et ceuq ue tu peu pas prendre, ensuite faut toujours raisonner avec cette phrase:
"je pars de A vers...." et de là, tu regrde le plus court: en pensant bien que tu peux parfois passer par plusieurs sommets et ce sera plus court qu'en direct...ca dépend des pondération des liens...
"Un seul Être vous manque, et tout est dépeuplé..."
sphaxslayer
Messages postés
216
Date d'inscription
mardi 5 avril 2005
Statut
Membre
Dernière intervention
17 septembre 2008
27 avril 2005 à 15:50
27 avril 2005 à 15:50
ah bah j'ai été pris d'court lol si t'as pigé le truc c le principal...ok j'vais voir si je les ai à portee d'mains et j'te scanne ca ;)
"Un seul Être vous manque, et tout est dépeuplé..."
"Un seul Être vous manque, et tout est dépeuplé..."
RM50Man
Messages postés
314
Date d'inscription
mercredi 1 novembre 2000
Statut
Membre
Dernière intervention
20 août 2006
27 avril 2005 à 16:56
27 avril 2005 à 16:56
Le but c a partir de A , trouver le chemin le plus court pour aller a chaque sommet!!!
C'est ca!!
RM50man
C'est ca!!
RM50man
sphaxslayer
Messages postés
216
Date d'inscription
mardi 5 avril 2005
Statut
Membre
Dernière intervention
17 septembre 2008
27 avril 2005 à 16:59
27 avril 2005 à 16:59
effectivement...j'aurais peut-être dû commencé par dire à quoi servait Dijkstra...
"Un seul Être vous manque, et tout est dépeuplé..."
"Un seul Être vous manque, et tout est dépeuplé..."
RM50Man
Messages postés
314
Date d'inscription
mercredi 1 novembre 2000
Statut
Membre
Dernière intervention
20 août 2006
27 avril 2005 à 18:24
27 avril 2005 à 18:24
A
B
C
D
E
F
G
H
I
J
K
L
A
0
18
12
25
62
32
B
59
0
59
23
2
37
42
54
C
68
0
75
42
24
26
5
D
5
19
51
0
15
30
41
89
25
E
53
2
0
6
46
79
2
40
5
F
49
48
0
7
79
G
1
52
94
0
93
H
51
75
61
0
84
I
73
98
5
40
0
60
J
66
41
71
60
93
0
25
K
26
72
27
66
0
11
L
56
9
72
22
92
0
A
B
C
D
E
F
G
H
I
J
K
L
A
0
18
12
25
62
32
B
59
0
59
23
2
37
42
54
C
68
0
75
42
24
26
5
D
5
19
51
0
15
30
41
89
25
E
53
2
0
6
46
79
2
40
5
F
49
48
0
7
79
G
1
52
94
0
93
H
51
75
61
0
84
I
73
98
5
40
0
60
J
66
41
71
60
93
0
25
K
26
72
27
66
0
11
L
56
9
72
22
92
0 Attention, vous avez le droit de recommencer si vous vous êtes trompé mais cela vous enlève des points.
Vous avez obtenu 10 (sur 10) points pour cette réponse.
L'algorithme est terminé.
On a obtenu la matrice ligne
dont le i-ième élément est égal au coût du plus court chemin du sommet A vers le i-ième sommet RM50man
sphaxslayer
Messages postés
216
Date d'inscription
mardi 5 avril 2005
Statut
Membre
Dernière intervention
17 septembre 2008
28 avril 2005 à 09:41
28 avril 2005 à 09:41
looool ca se la pèèète! :p
bah apparemment t'as compris....ca tombe bien parce que j'ai pas retrouvé mes cours...enfin j'ai qu'un controle (raté d'ailleurs) qui m'avait fait m'réveiller...apres ce foirage j'ai bossé à fond Dijkstra et du coup j'ai réussi :D
et bien tant mieux pour toi félicitation ;)
"Un seul Être vous manque, et tout est dépeuplé..."
bah apparemment t'as compris....ca tombe bien parce que j'ai pas retrouvé mes cours...enfin j'ai qu'un controle (raté d'ailleurs) qui m'avait fait m'réveiller...apres ce foirage j'ai bossé à fond Dijkstra et du coup j'ai réussi :D
et bien tant mieux pour toi félicitation ;)
"Un seul Être vous manque, et tout est dépeuplé..."