ZWeitkürzester Weg; Digraph

Neue Frage »

_freeangle_ Auf diesen Beitrag antworten »
ZWeitkürzester Weg; Digraph
Hi, ich habe ein Problem mit meinen Hausaufgaben.Vielleicht kann mit ja jemand helfen:

Gegeben sei ein Digraph G mit Gewichten c : E(G) --> und zwei Knoten s,t aus V(G): Der kürzeste Weg P von s nach t sei eindeutig. Kann man den kürzesten Weg von P verschiedenen Weg von s nach t in polynomialer Zeit bestimmen?

Ich habe irgendwie überhaupt keinen Ansatz
papahuhn Auf diesen Beitrag antworten »
RE: ZWeitkürzester Weg; Digraph
Weißt du, wie man den kürzesten Weg findet, und wieviel Zeit das benötigt? Angenommen du kennst eine Methode um den kürzesten zu finden. Überleg dann, wie man mit der gleichen Methode den zweitkürzesten finden kann.
_freeangle_ Auf diesen Beitrag antworten »
RE: ZWeitkürzester Weg; Digraph
Ja ich kenne den Algorithmus von Dijkstar und die Laufzeit beträgt ...
aber ich soll doch den kürzesten Weg von p verschiedenen finden... was hat das mit dem Zweitkürzesten zu tun
papahuhn Auf diesen Beitrag antworten »
RE: ZWeitkürzester Weg; Digraph
Der kürzeste von p verschiedene Weg ist doch der zweitkürzeste, wenn ich mich nicht irre. Aber egal, das ist ja bloß eine Bezeichnung. Ich nenne es weiterhin den zweitkürzesten.
Du kennst Dijkstra. Was bedeutet es, dass ein Weg von einem anderen verschieden ist? Was für Fälle können da eintreten?
_freeangle_ Auf diesen Beitrag antworten »

Hmm um ehrlich zu sein weiß ich es nicht... weiß nur dass man jeden Knoten abgeht vom Startpunkt aus und dass man den mit dem minimalsten Kantengewicht wählt... oder einen kürzesten Wege Baum finden kann womit man jeden Knoten in minimaler Zeit oder minimalen Kosten erreichen kann... ist vielleicht gar nicht so schlecht weil dann kann man alle kürzesten Wege sehen zu allen Knoten...
aber irgendwie weiß ich immer noch nicht so recht weiter... also ich denke schon dass es in polynomialer Zeit gefunden werden kann weiß aber nicht so richtig wie ich das erklären soll... wir hatten dazu auch nicht so richtig viel
papahuhn Auf diesen Beitrag antworten »

Tjo ich weiß jetzt nicht was ich noch sagen kann, ohne zuviel zu verraten. Ich bin ebenfalls der Meinung, dass das in Polynomzeit machbar ist.
 
 
_freeangle_ Auf diesen Beitrag antworten »

hmm naja ist es denn richtig, dass ich einen kürzesten Wege Baum erstelle mit dem Algorithmus von Dijkstra und dann einfach den Weg zum Zielknoten durchlaufe müsste doch dann einen Aufwand von O(n³) haben... und das wäre ja in polynomialer Zeit?!

Ich komme so nämlich auch nicht viel weiter weil irgendwie kann ich damit nix anfangen... schonmal gut dass ich weiß das ich das mit dem Algorithmus machen kann... das hilft ein wenig... aber ich bin mir nicht wirklich sicher
PrototypeX29A Auf diesen Beitrag antworten »

Ich kann mir nicht vorstellen dass das Problem NP-Schwer ist, sonst waere die Aufgabe verdammt heikel Augenzwinkern

Ich nehme an es muessen p unterschiedliche Wege gefunden (p-mal der gleiche waere etwas witzlos), dann muesste man sich ueberlegen wann ein Weg unterschiedlich ist.

Aber ich sehe auf anhieb auf keinen Algorithmus bei dem ich beweisen kann das er Polynomiale Laufzeit braucht. Wenn man den ersten Weg mit dem Weg der laenge l gefunden hat sucht man ja nun einen weg mit einer laenge > l, ich find leider nicht wie schwer dieses Problem ist.
PrototypeX29A Auf diesen Beitrag antworten »

Ich merk grad das ich die Aufgabenstellung etwas falsch gelesen hab, und ne groessere Anzahl von unterschiedlichen Wegen gesucht hab smile

Ich denke ich weiss eine Loesung die n mal so lange braucht wie P zu finden.
papahuhn Auf diesen Beitrag antworten »

Zitat:
Original von PrototypeX29A
Ich merk grad das ich die Aufgabenstellung etwas falsch gelesen hab, und ne groessere Anzahl von unterschiedlichen Wegen gesucht hab smile

Ich denke ich weiss eine Loesung die n mal so lange braucht wie P zu finden.


Dann haben wir wohl den gleichen Ansatz. Vielleicht fällt dir ein Tipp ein, ohne gleich die Lösung zu verraten.
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »