Frage: Dijkstra-Algorithmus anpassen, um das TSSP-Problem in einem gewichteten ungerichteten Graph zu lösen.Dijkstra-Algorithmus in ungerichteten Graphen ändern
sicherlich muss der Algorithmus nicht geändert werden? Wenn der Graph ungerichtet ist, dann ist es nur ein gerichteter Graph mit Kanten in beiden Richtungen, oder?
Ja, Dijkstras Algorithmus funktioniert für beide Arten von Graphen, und im ungerichteten Fall können Sie nur eine Kante von beiden Endpunkten verwenden.
Wenn Ihre Implementierung mit Graphen arbeitet, die von einer Adjazenzliste angegeben werden, dann ist diese Information bereits implizit durch diese Datenstruktur gegeben: Im ungerichteten Fall listen Sie für eine Kante (u, v) u in der Adjazenz von v auf und v in der Nähe von dir, die dir beide Richtungen gibt. Sie können also die gleiche Implementierung für beide Grafiktypen verwenden.
Mögliches Duplikat von [Ist Dijkstras Algorithmus für gerichtete oder ungerichtete Graphen?] (Https://stackoverflow.com/questions/38190592/is-dijkstras-algorithm-for-directed-or-iredirected-graphs) – Keiwan