Discussion:Arbre couvrant de poids minimal
Cet article est indexé par les projets Informatique et Mathématiques.
Les projets ont pour but d’enrichir le contenu de Wikipédia en aidant à la coordination du travail des contributeurs. Vous pouvez modifier directement cet article ou visiter les pages de projets pour prendre conseil ou consulter la liste des tâches et des objectifs.
| Avancement | Importance | pour le projet | |
|---|---|---|---|
| Bon début | Faible |  | Informatique (discussion • critères • liste • stats • hist. • comité • stats vues) |
| À évaluer |  | Mathématiques (discussion • critères • liste • stats • hist. • comité • stats vues) | |
Cet article comporte une liste de tâches suggérées :
Votre aide est la bienvenue pour corriger les arguments inconnus dans les appels de modèle, présents dans l'article :
- Modèle {{ Lien web }} : l'argument «
note=Manuscript available online (78 pages)» ne fait pas partie des arguments gérés par le modèle {{ Lien web }} (dans « Liens externes ») -- 7 août 2021 à 10:15 (CEST)
- Modèle {{ Lien web }} : l'argument «
Algorithme de Dijkstra?[modifier le code]
Euh, j'ai peur de dire une bêtise, mais l'algorithme de Dijkstra permet-il vraiment de trouver un arbre recouvrant de poids MINIMAL? J'insiste sur le "minimal" parce que je suis bien d'accord que l'on trouve, avec Dijkstra, un arbre couvrant le graphe, mais je ne suis vraiment pas sûr qu'il soit de poids minimal. Pour moi, on trouve juste un arbre qui minimise les chemins reliant la racine avec n'importe quel nœud de destination...
- C'est vrai, il n'y a pas de rapport. Contre-exemple : un carré ABCD avec d(A,B)=1, d(B,C)=3, d(C,D)=2 et d(D,A)=3. Exécuté à partir de A, l'algorithme de Dijkstra fournit un arbre contenant les deux arêtes de poids 3, ce qui n'est pas minimal. Dalnord (d) 15 décembre 2011 à 09:15 (CET)
- Exact, j'ai modifié de mémoire, je me suis trompé. Merci de la modification.Jimmy-jambe (d) 16 décembre 2011 à 18:47 (CET)
Une source[modifier le code]
Bonjour, je pensais développer cet article à fond, et puis l'envie est passée. Si quelqu'un a envie de le faire, je signale juste la source un peu cachée en fin d'article, de Jason, qui est très utile. --Roll-Morton (discuter) 19 avril 2016 à 09:32 (CEST)