1
Pourquoi certains chemins ont beaucoup plus/moins de poids que d'autres voies de longueur égale? Dans Dijkstra, la longueur et le poids du trajet ne sont-ils pas équivalents?
A
Répondre
4
Vous voulez dire que la représentation graphique de la ne correspond pas à la weight chaque chemin a? Ils n'ont pas trop ... la représentation visuelle n'est qu'une représentation, rien d'autre. Il n'est pas oblié être l'équivalent du poids.
Vous pouvez redessiner le graphique comme vous le souhaitez, en vous assurant simplement que les connexions entre les sommets sont conservées.
Edit: et peu importe le type de graphique que vous utilisez, que ce soit Dijkstra ou un autre. Vous pouvez même consulter des graphiques où la direction compte: de A à B, le poids peut être de 10 et de B à A, le poids peut être de 30. Aucun problème.
Édition 2: l'image montre simplement comment les sommets se connectent les uns aux autres. L'image n'a pas besoin d'être à l'échelle avec le graphique qui est stocké dans votre programme. Parfois, vous aurez des graphes avec autant de sommets et d'arêtes que vous ne serez pas en mesure de le représenter dans le bon sens. Ce qui compte pour vos problèmes de programmation, ce sont les sommets, les arêtes et les poids. L'image est juste une représentation grossière de celui-ci. Vous pouvez redessiner l'image comme vous voulez, vous devez juste vous assurer de mettre tous les sommets, tous les bords, et tous les poids pour chaque bord.
+0
Est-il possible avec Dijkstra d'égaliser les bords avec la distance ou sont-ils des problèmes complètement séparés? – daidai
+0
Si je comprends ce que vous voulez dire: les bords sont la distance entre deux sommets (si vous pensez dans une carte, comme les villes dans un pays). Ils peuvent aussi signifier «coût» (par exemple, passer d'un état «liquide» à un état «vapeur» coûte 100o Celsius). Ils peuvent signifier tout ce que vous aimez. Le poids des arêtes est le prix pour passer du sommet A au sommet B. – woliveirajr
+0
Existe-t-il des algorithmes/versions de Dijkstra où le bord est uniquement la longueur? Je ne vois toujours pas comment/pourquoi, dans l'exemple ci-dessus, voyager entre deux distances similaires "coûte" 3 et 16 unités. – daidai
2
La longueur du chemin (comme dans la taille de la ligne dans le diagramme) est sans importance, c'est seulement pour le rendre joli. Le poids de la ligne indique le coût de déplacement entre deux nœuds. Il est cependant déroutant, et vous pourriez faire longueur = poids en changeant la façon dont le graphique est dessiné.
+0
Pourquoi le coût de déplacement entre deux points plus proches serait, par exemple, 3 fois plus que deux autres points? C'est ce que je ne comprends pas. – daidai
+0
@daidai: La distance dans le 'graph' est spécifiée (les nombres que vous avez vu dans le graphique). Le graphique n'a pas besoin d'être à l'échelle avec les distances réelles. L'image que vous produisez pour représenter le graphique vous aide simplement à le représenter. – woliveirajr
+0
Ah vois Im devine Im essayant de faire l'inverse. Les graphiques sur l'exemple sont des représentations de lieux et les lignes sont censées être les distances approximatives entre eux - et Im en utilisant cet algorithme pour trouver le chemin le plus court entre deux endroits, via d'autres. Est-ce que la Dijkstra ne convient pas à mes besoins? – daidai
Questions connexes
- 1. L'algorithme de plus court chemin de Dijkstra ne fonctionnera pas
- 2. Boost Graph CRS: poids en vrac et Dijkstra
- 3. L'algorithme de Dijkstra pour trouver le chemin le plus pondéré
- 4. Algorithme de plus court chemin de Dijkstra Lars Vogel
- 5. Recherche du chemin le plus court entre les nœuds en utilisant Dijkstra et min heap C++
- 6. L'algorithme de Dijkstra sans vecteur "précédent"
- 7. Algorithme dijkstra utilisant Matlab
- 8. Dijkstra algorithme propriété
- 9. Algorithme de Dijkstra avec graphe de la liste d'adjacence
- 10. Implémentation de l'algorithme de Dijkstra
- 11. Exemple QuickGraph Dijkstra
- 12. Dijkstra et FileInput. Java
- 13. Python - Algorithme de Dijkstra
- 14. Problème d'algorithme de Dijkstra
- 15. L'algorithme de Dijkstra avec un tableau 2d
- 16. Algorithme de Dijkstra avec listes d'adjacence et file d'attente prioritaire
- 17. Algorithme des banquiers de Dijkstra
- 18. Heap dans l'algorithme de Dijkstra
- 19. L'algorithme de Dijkstra dans CUDA
- 20. Pourquoi un * plus rapide que Dijkstra
- 21. poids minimum T de sous-ensemble relié des bords algorithme
- 22. Comment restreindre l'algorithme du plus court chemin - dijkstra avec un coût maximum?
- 23. Dijkstra plus court chemin avec VertexList = ListS dans le graphique boost
- 24. Dijkstra: Recherche du chemin le plus court dans le graphe orienté
- 25. Boost dijkstra shortest_path - comment obtenir le chemin le plus court et pas seulement la distance?
- 26. Algorithme Dijkstra avec file d'attente à priorité min
- 27. multiples chemins les plus courts en utilisant Dijkstra
- 28. Comment optimiser le code Dijkstra en PHP?
- 29. Performance de l'implémentation de l'algorithme de Dijkstra
- 30. Algorithme de routage différent de Dijkstra-concept
Par hasard, voulez-vous dire des arêtes quand vous dites des chemins? –
@obrok: probablement ... – woliveirajr
Comment avez-vous généré ce graphique? – Peaches491