Hallo zusammen,
ich bin am überlegen, wie hoch die Komplexität ist bei der Erschließung eines
kürzesten Weges.
Also angenommen wir haben einen unvollständigen Graphen mit n-Knoten und
e-Kanten, wie komplex wäre es dann den kürzesten Weg herauszufinden, ähnlich im
Stil des TSP, das ja in einem vollständigen Grafen normalerweise abläuft und
von der Komplexität n! ist.
Gruß Mike
Hallo Mike.
Wenn ich mich recht erinnere, lässt sich das Lösen eines TSP für unvollständige Graphen auf das Lösen eines TSP für vollständige Graphen zurückführen. Dafür wird der unvollstänige Graph vervollständigt indem für die fehlenden Kanten ausreichend hoch gewichtete Kanten eingefügt werden.
Falls nun eine TSP-Tour gefunden wird, kann anhand deren Länge entschieden werden, ob auch im unvollständingen Ausgangsgraphen diese Tour vorhanden ist, oder eben nicht.
Die Komplexität für das Lösen des TSP selbst verändert sich dadurch natürlich nicht, allerdings muss man das Auffüllen des unvollständigen Graphen noch berücksichtigen.
Gruß,
Chris
Hallo Mike,
der kürzeste Weg in einem Graphen mit n Knoten und m Kanten läßt sich in
Zeit O(m + n log n) berechnnen, ist also definitiv einfacher als TSP 
http://de.wikipedia.org/wiki/Dijkstra-Algorithmus
Als untere Schranke (=Welche Rechenzeit benötigt der beste,denkbare Algorithmus?) scheint es nur Omega(m+n) zu geben (Die Eingabe muss halt gelesen werden).
Da der Dijkstra-Algorithmus die Kanten sortiert, ist die interessante Frage, ob es einen Kürzesten-Wege-Algorithmus gibt, der ohne Sortieren auskommet und dann besser als Omega(n log n) wäre. Ist anscheinend noch unbekannt, wie in diesem Übersichtspaper von 2001 beschrieben ist:
http://citeseer.ist.psu.edu/681179.html
Grüße
Thorsten
[Bei dieser Antwort wurde das Vollzitat nachträglich automatisiert entfernt]