Graphen, kürzeste Wege |
| 09.01.2008, 16:07 | Auf diesen Beitrag antworten » |
| JROppenheimer | Graphen, kürzeste Wege Ich arbeite gerade daran, zu beweisen, dass ein "kürzester" Pfad in einem Graphen, wenn der Graph eine neue Gewichtsfunktion bekommt, immernoch der kürzeste Pfad ist... Stellt sich mir folgende Frage: "kürzester Pfad" heisst doch immer "kürzester Pfad" von einem BESTIMMTEN Startknoten aus, oder? Heisst es nicht sogar, von einem BESTIMMTEN KNOTEN, zu einem anderen BESTIMMTEN knoten!? |
|
|
|
| 09.01.2008, 17:42 | Auf diesen Beitrag antworten » |
| Tobias | Das klingt in vielerlei Hinsicht -man entschuldige die Wortwahl- nach Bullshit. 1.) Jeder Pfad hat selbstverständlich festgelegte Start- und Endknoten. Würde man den Startknoten festlegen, den Endknoten jedoch nicht, ist der kürzeste Pfad immer der Nullpfad zu sich selbst. Um das Problem also klar zu formulieren: Gegeben sind zwei Knoten a, b in einem (gewichteten) Graphen G. Ziel: Finde kürzesten Pfad von a nach b. 2.) Die Kosten eines Pfades sind (nach der mir bekannten Definition) abhängig von der gegebenen Gewichtsfunktion. Das bedeutet in direkter Folge, dass ein kürzester Pfad nach Austausch der Gewichtsfunktion nicht mehr der kürzeste sein muss. Einfaches Gegenbeispiel: Gegeben sind drei Knoten und jeder der Knoten ist mit den beiden anderen verbunden ( |
| 09.01.2008, 19:26 | Auf diesen Beitrag antworten » |
| JROppenheimer | es sing überhaupt nicht um die gewichtsfunktion an sich. es ging im allgemeinen darum, dass sssp die kürzesten pfade zu allen anderen erreichbaren pfaden findet. und dass in solch einem zusammenhang start und endknoten sich nciht ändern, auch, wenn durch änderung der gewichtsfunktion ein neuer pfad kürzester ist. in meinem fall ist die neue gewichtsfunktion so definiert, dass es eben so ist, dass ein kürzester pfad, kürzester pfad bleibt. war nirgends die rede von, wie die gewichte verteilt sind, oder geändert werden! einzig und allein die tatsache, dass eben diese beiden pfade start und ende gemeinsam haben machen es in meinem beispiel möglich das zu zeigen, NCIHT allgemein, sondern für dieses beispiel 2er gewichtsfunktionen. |
| 09.01.2008, 19:34 | Auf diesen Beitrag antworten » |
| Tobias | Aha, gleich mehrere neue Informationen auf einmal. SSSP (Single Source Shortest Path) berechnet zu einem gegebenen Startknoten die kürzesten Wege zu allen möglichen Endknoten. Wo soll sich deiner Meinung nach hier was an den Knoten ändern? Ein Pfad von a nach b ist ein Pfad von a nach b, egal wie lang er ist. Das du das auf eine konkrete Situation beziehst (und nicht allgemein meinst), hättest du auch mal erwähnen können. |
| Anzeige | |
|
|
|
| 10.01.2008, 10:57 | Auf diesen Beitrag antworten » |
| JROppenheimer | Sorry, für meine Ungenauigkeit. Ich hätte eine weitere Frage: Wenn es um "kürzeste" Wege geht, ist die Distanz, die damit dann minimal ist, immer eine Summe?! Angenommen ich habe einen Pfad, der von q über r und s nach t führt. Ist es immer so, dass sich die Kosten summieren?? d(q,r) + d(r,s) + d(s,t), wenn d() Gewicht oder Länge der Kante ist Oder ist das definitionsabhänig? Mir fehlt mal wieder das elementare Verständnis für Graphen und sowas i.a. |
| 10.01.2008, 13:09 | Auf diesen Beitrag antworten » |
| Tobias | Im Prinzip ist alles definitionsabhängig. Wenn jedoch keine Definition vorhanden ist, muss man annehmen, dass eine allgemeine Übereinkunft über den verwendeten Fachdeterminismus existiert. Im Falle der Kosten (oder Länge) eines Pfades ist die mir bekannte Definition die Aufsummierung der am Pfad partizipierenden Kantengewichte. Also liegst du richtig. |
| 10.01.2008, 13:24 | Auf diesen Beitrag antworten » |
| JROppenheimer | klasse, ich danke Dir! |
|
|
