Discussion :

[seli400]

Bonjour,

Je n'ai pas trouvé où écrire les sujets concernant la recherche opérationnelle, donc j'ai opté pour le forum conception.

Si je me trompe, orientez-moi vers le bon forum .

Voilà mon problème :

je voudrais trouver l'algorithme qui détermine l'arborescence des plus courtes distances issues d'un sommet 'i'.

J'ai cherché et j'ai trouvé que l'algorithme de Kruskal qui me donne l'arbre de poids minimum.

Merci de me répondre.

[Invité]

Bonjour,
Pour ce type de calcul j'ai utilisé l'algorithme de Dijkstra.
C'est très efficace.

[seli400]

Bonjour merci de me repondre
l'algorithme de dijkistra determine le chemin pas larborescence ?
ou bien c'est la meme chose?
une arborescence c'est quoi, un chemin??

[Invité]

En fait, quels quoi les termes, l'important est de savoir ce que vous voulez faire.
Par arborescence on sous-entend qu'il y a une origine et que une branche peut donner naissance à plusieurs branches. Donc, par définition, il n'y a qu'un seul chemin pour aller d'un point quelconque à une extrémité donnée.

Un graphe est un réseau maillé.
Il existe un grand nombre de chemins pour aller d'un point à un autre dans ce réseau, mais il en existe un qui est meilleur que les autres.

Par "arborescence des plus courtes distances issues d'un sommet", on peut comprendre "l'ensemble des chemins (les meilleurs) les plus courts pour aller du sommet 'i' à chacun des points destination "p" de la périphérie.

[seli400]

bonjour
est il faut d'uiliser l'algorithme de Kruskal qui determine l'arbre du poids le plus minimum??

[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

[Invité]

Bonjour,
Une arborescence est une représentation et une relation du type père-fils.
Il n'y a pas d'arborescence plus courte qu'une autre, ou de plus courte distance, ou je ne sais quoi. Une arborescence est ce qu'elle est, rien de plus, ni de moins.
On pourra peut-être vous aider si vous nous dites ce que vous voulez faire. Si c'est seulement appliquer un algorithme, alors appliquez le, si c'est pour faire dire par quelqu'un que c'est celui-là qu'il faut appliquer sans savoir pourquoi, alors vous vous êtres trompé de sous-forum.

[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