Discussion :

[seli400]

est ce qu'on peux determiner une arborescence du plus courte distance avec l'algorithme de Dijkistra??

[Aleph69]

Bonsoir,

définis mieux ton problème : de quelles données disposes-tu, que veux-tu calculer?

[seli400]

Bonjour,
Considérons le graphe suivant avec 7 sommets de S1 jusqu'a S7, muni de poids pour chaque arc du graphe.


S2 S6

S1 S4 S7

S3 S5

Question:
Déterminez l'arborescence des plus courtes disatnces issues du sommet1

PS: Pour legraphe les arcs sont reliés avec des traits

[biaggi]

Bonjour,

L'application de l'algorithme de Dijkstra peut en effet te permettre de répondre à ta question ; sous réserve que toutes les distances des arcs de ton graphe soient positives ou nulles.

L'exemple de Wikipédia est assez illustratif.

Pour ton cas d'utilisation (plus court chemin depuis S1 vers tous les autres sommets), tu dois utiliser l'algorithme de Dijkstra avec comme cas d'arrêt: "tous mes sommets ont été sélectionnés".
Si tu venais à chercher le plus court chemin entre S1 et UN autre sommet (par exemple S5), tu utiliserais le même algorithme de Dijkstra avec cette fois-ci comme cas d'arrêt: "S5 est sélectionné"

PS : pour faciliter tes recherches, note bien le bon orthographe: Dijkstra

[seli400]

donc l'algorithme de Kruskal ne repond pas au probléme??celui qui detemine l'arbre du plus court chemi???

[biaggi]

L'algorithme de Dijkstra et celui de Kruskal n'ont pas le même but.

L'algorithme de Dijkstra sert à calculer les plus courts chemins entre toute paire de sommets d'un graphe (à valuations toutes positives ou nulles).

Exemple de solutions : Le plus court chemin pour relier Nantes et Paris consistent à sélectionner la route Nantes - Le Mans (150 Kms) puis Le Mans - Paris (250 Kms), pour une distance totale de 400 kilomètres.

Autres définition et exemple : ici


L'algorithme de Kruskal est un algorithme de recherche d'arbre recouvrant de poids minimum. Pour vulgariser, on cherche à créer le réseau d'arcs de moindre coût interconnectant tous les sommets d'un graphe.

Exemple de solution : en optimisant le nombre de kilomètres, l'arbre recouvrant de poids minimum pour que les 3 villes Nantes, Le Mans et Paris soient reliées consiste à sélectionner les routes Nantes - Le Mans et Le Mans - Paris. Avec ces seules deux routes, les 3 villes sont interconnectées, i.e. je peux aller de Nantes vers Le Mans et Paris, du Mans vers Nantes et Paris, et de Paris vers Nantes et Le Mans.

Autres définition et exemple : ici

J'espère t'avoir un peu aiguillé... Regarde les liens que je t'ai fournis (et d'autres si nécessaire...) et pose toi la question de savoir ce que tu cherches exactement. Le choix de l'algorithme à utiliser t'apparaîtra alors.

[seli400]

est s'il s'agit de determiner l'aroberssence du plus court chemin,on fait Kruskal ou bien Dijkistra??

[seli400]

est s'il s'agit de determiner l'aroberssence du plus court chemin,on fait Kruskal ou bien Dijkistra??

[biaggi]

Comme te l'a expliqué Pierre Dolez dans la discussion "La Recherche Opérationnelle" que tu as créée sous ce même forum ( ici ), et où tu poses exactement la même question... : rechercher une arborescence des plus courtes distances n'a pas de sens.

Je t'ai donné, je pense, deux introductions détaillées aux algorithmes de Dijkstra et Kruskal (en te proposant aussi des liens pour davantage d'explications). Je crois que le mieux est que désormais tu regardes de plus près ces liens et que tu te fasses une idée sur la nature exacte de ton problème.

A titre personnel (désolé pour les autres lecteurs de polluer ainsi le fil de la discussion), sache aussi que les gens seront plus enclins à t'aider si tu ne fais pas plusieurs posts sur le même sujet en ne changeant que le titre, et si tu considères plus les explications qu'ils essaient de te fournir...

[Invité]

est s'il s'agit de determiner l'aroberssence du plus court chemin,on fait Kruskal ou bien Dijkistra??

Pour le savoir, à votre place, je "ferais" les deux. Moi, je ne sais pas ce que vous voulez faire, je suppose que vous, vous le savez.

Après un petit moment de réflexion et pour essayer d'être sympa.
La question de l'exercice est parfaitement claire et bien posée, pourquoi ne faites-vous pas ce que vous demande votre professeur?
Manifestement, celui-ci ne vous demande pas d'aller à la pêche aux informations, de trouver des solutions toutes faites, de répéter, forcément plus mal, ce que d'autres ont mis au point en réfléchissant.
La solution de cet exercice est très simple, mais ne comptez pas sur moi pour vous la donner, vous devez la trouver tout seul.

[seli400]

bonjour
excusez moi je savais pas que c'était interdit,de poster dans de diferents forum vu que ka recherche opérationnelle n'a pas de sujet de discussion specialisé donc je voulais maximiser mes chances de trouver des réponses a ma question
je demande des excuses a l'admpinstrateur meme...

[biaggi]

bonjour
excusez moi je savais pas que c'était interdit,de poster dans de diferents forum vu que ka recherche opérationnelle n'a pas de sujet de discussion specialisé donc je voulais maximiser mes chances de trouver des réponses a ma question
je demande des excuses a l'admpinstrateur meme...

Il ne s'agissait pas de te blâmer mais de t'indiquer qu'au contraire, je pense qu'en multi-postant dans un même forum, tu minimises tes chances de réponse car les personnes désireuses d'aider pourraient alors perdre l'envie de t'aider.
De plus, l'intérêt d'un tel forum est aussi d'aider les personnes ayant les mêmes difficultés que toi, dans un futur plus ou moins proche, à trouver les réponses à tes questions. Et si tu multi-postes, cela devient un flou artistique où on peut se perdre. Bref, arrêtons-là pour cela et revenons-en à ce qui nous intéresse...

Je te conseille de regarder des exemples d'application (par exemple ceux que je t'ai mentionnés) des algorithmes de Dijkstra et Kruskal pour comprendre à quoi ils servent et ainsi déterminer celui qui s'applique le plus à ton problème.

A mon humble avis, et pour t'aider un peu plus, ton professeur (s'il s'agit bien d'un exercice) demande que tu listes les plus courts chemins depuis S1 vers tous les autres sommets.

[seli400]

vous comprenez l'histoire d'une façon contradictoire,j'ai jamais chercher à ce qu'on me donne des réponses faites pour des problémes que j'ai eut a l'école, j'ai quiter l'école y'a bien des lustres,j'ai passer y'a quelque jours un examin pour recrutement et le module de la recherche opérationnelle nous à été proposé.
donc pour revenir a ma question on nous adonner un exercice dont l'intitulé de la question est comme telle:

un schema de graphe nous a été donneé, du sommet S1 jusqu'au sommet S7
Déterminez l'arborescence des plus courtes distances issues du sommet1
ma réponse été d'appliquer l'algorithme de kruskal qui nous donner l'arbre couvrant de poid minimum,et y'vais queleque collégues a moi qui ont apliquer l'algorithme de dijkitra donc je voulais un avis d'un connaisseurs dans le domaine et
voilà toute l'histoire

[biaggi]

Avec l'historique complet, on comprend mieux l'ambiguïté de tes questions et remarques...

A mon avis, la manière de poser la question de l'exercice est hasardeuse et prête à confusion (la preuve, nous sommes au moins deux sur ce forum à ne pas l'avoir comprise directement).

Pour ma part, je pense qu'il fallait lister les plus courts chemins depuis S1 vers tous les autres sommets. La solution se résume alors à :

• Plus court chemin de S1 vers S2 est :...
• Plus court chemin de S1 vers S3 est :...
• Plus court chemin de S1 vers S4 est :...
• Plus court chemin de S1 vers S5 est :...
• Plus court chemin de S1 vers S6 est :...
• Plus court chemin de S1 vers S7 est :...

Pour trouver les plus courts chemins à proprement parler (et si le graphe est composé d'arcs ou arêtes à valuation positive ou nulle), on peut appliquer l'algorithme de Dijkstra en utilisant comme cas d'arrêt "tous les sommets ont été explorés".