ZWeitkürzester Weg; Digraph |
09.05.2006, 19:09 | _freeangle_ | Auf diesen Beitrag antworten » | ||
ZWeitkürzester Weg; Digraph 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 |
||||
09.05.2006, 19:24 | 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. |
||||
09.05.2006, 19:35 | _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 |
||||
09.05.2006, 19:42 | 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? |
||||
09.05.2006, 19:50 | _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 |
||||
09.05.2006, 20:21 | 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. |
||||
Anzeige | ||||
|
||||
09.05.2006, 22:53 | _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 |
||||
10.05.2006, 10:37 | PrototypeX29A | Auf diesen Beitrag antworten » | ||
Ich kann mir nicht vorstellen dass das Problem NP-Schwer ist, sonst waere die Aufgabe verdammt heikel 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. |
||||
10.05.2006, 12:59 | 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 Ich denke ich weiss eine Loesung die n mal so lange braucht wie P zu finden. |
||||
10.05.2006, 16:22 | papahuhn | Auf diesen Beitrag antworten » | ||
Dann haben wir wohl den gleichen Ansatz. Vielleicht fällt dir ein Tipp ein, ohne gleich die Lösung zu verraten. |
|
Verwandte Themen
Die Beliebtesten » |
Die Größten » |
Die Neuesten » |