Dijkstra Algorithmus?
Hello Leute, was passiert beim Dijkstra Alg wenn der Graph zwei Zusammenhangskomponenten hat? Irgendwann gibt es ja keine Nachfolger mehr, aber die Knoten von der anderen Zusammenhangskomponente wurden ja noch nicht besucht. Ist dann der Algorithmus beendet und es gibt einfach keine Lösung? Danke im Voraus
2 Antworten
Von gutefrage auf Grund seines Wissens auf einem Fachgebiet ausgezeichneter Nutzer
Informatik, Algorithmus
Natürlich ist er beendet, denn Dijkstra ist ein SSSP,-Algorithmus und was nicht erreichbar ist hat eben Distanz unendlich.
Dann liefert der Algorithmus als Distanz ja unendlich was auch stimmt?
Du suchst ja die Distanz von einem knoten zu allen anderen. Wenn der Knoten in der Zussamenhangskomponente A liegt ist die Distanz von ihn zu allen Knoten aus Komponente B offensichtlich unendlich.