"Kürzester Weg" in P?
-
Kürzestester Weg ist in NP.
-
Zuerst einmal müsste man definieren, was genau mit "kürzester Weg" gemeint sein soll. Der kürzeste Weg zwischen zwei Knoten? Der kürzeste von allen möglichen Wegen im Graphen? Der kürzeste Weg der eine bestimmte Menge von Knoten einschließt? Um was für einen Graphen geht es überhaupt?
gerichtet, ungerichtet, gewichtet, ungewichtet, nur positive Gewichte, ...?
-
trollolol schrieb:
Kürzestester Weg ist in NP.
...und auch in PSPACE!!!
-
-
... wobei ... wenn man einen gewichteten Graphen mit positiven und negativen Kantengewichten zulässt, wird's ekelig mit dem "kürzesten Weg". Ich weiß es gerade nicht, aber es würde mich nicht wundern, wenn dazu kein "effizienter" Algorithmus bekannt ist.
-
Doch, doch. Die Algorithmen von Floyd-Warshall oder Bellman-Ford (für Graphen mit negativen Zyklen) machen das.
-
trollolol schrieb:
Kürzestester Weg ist in NP.
Laengster Weg ist in NP
*Edit
Da schon Algorithmen genannt wurden, die das Problem loesen, sollte man noch den Dijkstra Algorithmus nennen. Dieser funkitoniert allerdings nur bei positiven Kantengewichten.
-
JFB schrieb:
für Graphen mit negativen Zyklen
Wie definierst du denn den kleinsten Abstand in einem negativen Kreis? :p
Außerdem sind alle genannten Algorithmen für den ungerichteten Fall.
-
@Michael E.: Jaja, ich meinte (und deinem Smiley entnehme ich du wusstest das auch? ) damit, dass Bellman-Ford Kreise mit negativem Gewicht erkennt, Floyd-Warshall dagegen ein falsches Ergebnis liefert.
Sicher, dass Bellman-Ford und Floyd-Warshall nur im ungerichteten Fall korrekt arbeiten?
-
Es war natürlich gerichtet gemeint. Eine kurze Übersicht:
Ohne Kantengewichte kann man das Problem im gerichteten und ungerichteten Fall natürlich in linearer Zeit mit Breitensuche lösen. Hat man positive Kantengewichte, funktioniert Dijkstra im gerichteten und ungerichteten Fall. Bei konservativen Gewichten - negative Kantengewichte erlaubt, aber keine negativen Kreise - funktioniert Bellman-Ford nur im gerichteten Fall. Denn ersetzt man eine ungerichtete negative Kante durch zwei gegenläufige gerichtete, hat man auf einmal einen negativen Kreis und Bellman-Ford versagt. Stattdessen reduziert man das Problem auf Matchings und erreicht so eine Laufzeit von O(n^3). Bei beliebigen Kantengewichten ist das Kürzeste-Wege-Problem, entsprechend umdefiniert, NP-schwer, weil man negativen Kreisen aus dem Weg gehen muss.Edit: Für Floyd-Warshall gilt dasselbe wie für Dijkstra: Da er nur auf konservativen Gewichten funktioniert, kann man nicht einfach eine ungerichtete Kante durch zwei gerichtete ersetzen.