anwenden Ich weiß, dass Bellman-Ford-Algorithmus für gerichtete Graphen funktioniert aber nur für Info möchte ich wissen, ob es für ungerichtete Grafik funktioniert? Da mit Ungerichtetem Graphen keine Zyklen erkannt werden können, werden parallele Kanten als Cycles !! betrachtet. Bitte klären Sie.Können wir Bellman Ford-Algorithmus auf ungerichtete Graph
Antwort
In der Tat ist jeder ungerichtete Graph auch ein gerichteter Graph.
Sie müssen nur die Kanten {u, v} zweimal angeben (u, v) und (v, u).
Aber vergessen Sie nicht, dass dies auch bedeutet, dass jede Kante mit einem negativen Gewicht als eine Schleife zählt. Da der Bellman-Ford-Algorithmus NUR auf Graphen arbeitet, die keine Zyklen mit negativen Gewichten enthalten, bedeutet dies, dass Ihr nicht gerichteter Graph keine Kanten mit negativem Gewicht enthalten darf.
Wenn es nicht gut ist, Bellmann-Ford zu verwenden.
Um dies näher auszuführen - da der Graph nur nichtnegative Kanten haben muss, bedeutet das, dass Sie vielleicht stattdessen den Dijkstra-Algorithmus verwenden möchten, da er asymptotisch schneller ist. – templatetypedef
Ich habe die gleichen Zweifel. Danke für die Klarstellung. – whitehat
- 1. Sind Bäume gerichtete oder ungerichtete Graphen?
- 2. Graphite Graph - wie schnell können wir die Grafik aktualisieren?
- 3. JGraphT vermeiden Schleifen (Bellman Ford)
- 4. Django ungerichtete Grafik
- 5. Wie können wir facebook Anzeige mit Graph api-Explorer auf der Basis von date_stop
- 6. Yens Verbesserung Bellman-Ford
- 7. Abfrage bezüglich bellman ford
- 8. Wie können wir Sprite auf iPhone schütteln?
- 9. Können wir Resteasy auf jdk 1.5
- 10. können wir Breite li
- 11. Implementieren Bellman-Ford-Algorithmus C++
- 12. Wie können wir fb Benutzer Zeitzone mit fb Absender-ID mit Graph API?
- 13. können wir telefonieren im iphone?
- 14. Was ist der Unterschied zwischen dem minimalen Spanning-Tree-Algorithmus für ungerichtete vs gerichtete Graphen?
- 15. Können wir Facebook programmatisch abmelden
- 16. Leistung von Bellman-Ford kürzester Weg Algorithmus
- 17. Microsoft Graph - Benutzerprofile können nicht angezeigt werden
- 18. Können wir & in URL verwenden?
- 19. Warum können wir nicht "..." umkehren?
- 20. Können wir 100% Entkopplung erreichen?
- 21. Können wir über Typklassen abstrahieren?
- 22. Können wir Tastaturen programmgesteuert ändern
- 23. Wie können wir Kibana abfragen?
- 24. Wie wir den Diagrammtyp passieren können dynamisch
- 25. Wie können Graph API-Felderweiterungen kombiniert werden?
- 26. Können wir wissen, ob wir mit youtube api streamen?
- 27. Johnsons Algorithmus Graph Erklärung
- 28. Erhöhung Directed Graph - add_edge - stored_edge_property
- 29. Wie können wir anderen Browser auf einmal in Robot Framework
- 30. Welche addTarget-Aktionen können wir auf UITextView anwenden?
Schauen Sie sich [this] (http://stackoverflow.com/questions/14538403/shortest-path-algorithms-for-undirected-graph) an. – Nik