Dijkstra < Algor.+Datenstr. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 17:14 Do 01.03.2007 | | Autor: | Bastiane |
Hallo!
Eigentlich weiß ich, wie Dijkstra funktioniert, bin mir aber bei den Feinheiten doch nicht mehr ganz sicher. Habe mal versucht, das ganze ganz unmathematisch mit Worten zu beschreiben, könnte mal jemand gucken, ob das so richtig ist?
Mir ist klar, dass das so nicht gut geschrieben ist, aber ich will nur wissen, ob das so richtig ist:
"Der einfachste Algorithmus für die Bestimmung kürzester Wege von einem Ausgangsknoten zu allen anderen Knoten ist der Algorithmus von Dijkstra. Er hat in jedem Schritt zwei Mengen von Knoten gespeichert: die erste enthält alle Knoten, die komplett abgearbeitet sind, ihre kürzesten Wege zum Startknoten sind bereits bestimmt und ihre Nachfolger wurden in der zweiten Menge gespeichert. In dieser zweiten Menge befinden sich alle Nachfolgerknoten von bereits betrachteten Knoten, ihr kürzester Weg zum Startknoten ist noch nicht bestimmt bzw. kann noch verkürzt werden. In jedem Schritt wird der Knoten aus der zweiten Menge betrachtet, für den der Nachfolgerknoten den kürzesten Weg von allen noch nicht fertig bearbeiteten Knoten hat. Die Nachfolger dieses Knotens aus der zweiten Menge werden alle in die zweite Menge aufgenommen und ihr kürzester Weg auf den kürzesten Weg des Vorgängerknotens plus das Kantengewicht zwischen diesen beiden Knoten gesetzt. Der Knoten selber wird in die erste Menge "rübergeschoben" - er ist fertig bearbeitet."
Viele Grüße
Bastiane
![[cap]](/images/smileys/cap.gif "[cap]")
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 17:44 Do 01.03.2007 | | Autor: | Frank05 |
> Mir ist klar, dass das so nicht gut geschrieben ist, aber
> ich will nur wissen, ob das so richtig ist:
>
> "Der einfachste Algorithmus für die Bestimmung kürzester
> Wege von einem Ausgangsknoten zu allen anderen Knoten ist
> der Algorithmus von Dijkstra.
Schon falsch :-P
Mit Floyd-Warshall kann man zB viel einfacher von allen Knoten zu allen anderen die minimale Distanz berechnen (als Nebeneffekt des Bildens der transitiven Hülle), was aber natürlich eine deutlich schlechtere Komplexität hat.
> Er hat in jedem Schritt zwei
> Mengen von Knoten gespeichert: die erste enthält alle
> Knoten, die komplett abgearbeitet sind, ihre kürzesten Wege
> zum Startknoten sind bereits bestimmt und ihre Nachfolger
> wurden in der zweiten Menge gespeichert.
Zu diesem Zeitpunkt der Beschreibung ist jemandem, der den Algorithmus noch nicht kennt wohl nicht wirklich klar, was hier mit 'Nachfolger' gemeint ist.
> In dieser zweiten
> Menge befinden sich alle Nachfolgerknoten von bereits
> betrachteten Knoten, ihr kürzester Weg zum Startknoten ist
> noch nicht bestimmt bzw. kann noch verkürzt werden.
> In
> jedem Schritt wird der Knoten aus der zweiten Menge
> betrachtet, für den der Nachfolgerknoten den kürzesten Weg
> von allen noch nicht fertig bearbeiteten Knoten hat.
Welchen kürzesten Weg meinst du denn genau hier? *Dummstell*: Ich kenne den Weg bis zu meinem Startknoten für diese Nachfolgerknoten doch noch gar nicht.
> Die Nachfolger dieses Knotens aus der zweiten Menge werden alle
> in die zweite Menge aufgenommen und ihr kürzester Weg auf
> den kürzesten Weg des Vorgängerknotens plus das
> Kantengewicht zwischen diesen beiden Knoten gesetzt.
Und wenn der Graph einen Zyklus hat, dann fehlt hier und im Satz vorher noch irgendwo eine Möglichkeit, damit das Verfahren auch terminiert. So nehme ich immer wieder einen Knoten und werfe immer wieder seine Nachfolger in die zweite Menge um wieder weiterzumachen.
> Der Knoten selber wird in die erste Menge "rübergeschoben" - er ist fertig bearbeitet."
Ich weiß ja nicht für wen diese Beschreibung gedacht ist, aber es hätte schon seine Vorteile das ganze etwas formaler anzugehen. Wenn etwas mehr Grundwissen vorausgesetzt werden kann, dann kannst du statt dieser "zweiten Menge" und der Auswahl mit dem kürzesten Weg auch gleich klipp und klar sagen, dass hier eine Priority Queue vorliegt.
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 18:08 Do 01.03.2007 | | Autor: | Bastiane |
Hallo Frank!
Danke für deine Kommentare.
> > "Der einfachste Algorithmus für die Bestimmung kürzester
> > Wege von einem Ausgangsknoten zu allen anderen Knoten ist
> > der Algorithmus von Dijkstra.
>
> Schon falsch :-P
> Mit Floyd-Warshall kann man zB viel einfacher von allen
> Knoten zu allen anderen die minimale Distanz berechnen (als
> Nebeneffekt des Bildens der transitiven Hülle), was aber
> natürlich eine deutlich schlechtere Komplexität hat.
Ich will aber nur die Wege von einem Knoten zu allen anderen. Dafür mache ich es doch nicht so umständlich und berechne das für alle Knoten! ![[aetsch]](/images/smileys/aetsch.gif "[aetsch]")
> > Er hat in jedem Schritt zwei
> > Mengen von Knoten gespeichert: die erste enthält alle
> > Knoten, die komplett abgearbeitet sind, ihre kürzesten Wege
> > zum Startknoten sind bereits bestimmt und ihre Nachfolger
> > wurden in der zweiten Menge gespeichert.
>
> Zu diesem Zeitpunkt der Beschreibung ist jemandem, der den
> Algorithmus noch nicht kennt wohl nicht wirklich klar, was
> hier mit 'Nachfolger' gemeint ist.
Dieser jemand kennt aber den Algo.  (siehe unten) Außerdem geht es doch um gerichtete Graphen, und da ist doch klar, was ein Nachfolger ist!?
> > In dieser zweiten
> > Menge befinden sich alle Nachfolgerknoten von bereits
> > betrachteten Knoten, ihr kürzester Weg zum Startknoten ist
> > noch nicht bestimmt bzw. kann noch verkürzt werden.
>
> > In
> > jedem Schritt wird der Knoten aus der zweiten Menge
> > betrachtet, für den der Nachfolgerknoten den kürzesten Weg
> > von allen noch nicht fertig bearbeiteten Knoten hat.
>
> Welchen kürzesten Weg meinst du denn genau hier?
> *Dummstell*: Ich kenne den Weg bis zu meinem Startknoten
> für diese Nachfolgerknoten doch noch gar nicht.
Da hast du Recht. Da könnte ich hinzufügen, dass der Weg gemeint ist, der sich ergibt, wenn ich die "letzte" Kante hinzufüge. Ist natürlich auch nicht wirklich gut formuliert.
> > Die Nachfolger dieses Knotens aus der zweiten Menge werden
> alle
> > in die zweite Menge aufgenommen und ihr kürzester Weg auf
> > den kürzesten Weg des Vorgängerknotens plus das
> > Kantengewicht zwischen diesen beiden Knoten gesetzt.
>
> Und wenn der Graph einen Zyklus hat, dann fehlt hier und im
> Satz vorher noch irgendwo eine Möglichkeit, damit das
> Verfahren auch terminiert. So nehme ich immer wieder einen
> Knoten und werfe immer wieder seine Nachfolger in die
> zweite Menge um wieder weiterzumachen.
Mmh, aber sobald für einen Knoten alle Nachfolger in die Menge geworfen wurden, wird der Knoten doch in die erste Menge rübergeschoben und somit nie wieder betrachtet!?
> > Der Knoten selber wird in die erste Menge "rübergeschoben"
> - er ist fertig bearbeitet."
>
> Ich weiß ja nicht für wen diese Beschreibung gedacht ist,
> aber es hätte schon seine Vorteile das ganze etwas formaler
> anzugehen. Wenn etwas mehr Grundwissen vorausgesetzt werden
> kann, dann kannst du statt dieser "zweiten Menge" und der
> Auswahl mit dem kürzesten Weg auch gleich klipp und klar
> sagen, dass hier eine Priority Queue vorliegt.
Nene, die Sache ist ganz allein für mich. So, dass ich mir das merken kann. Worte lassen sich besser merken als Formeln, und ausführlichere Beschreibungen - auch wenn sie um 10 Ecken gedacht und somit sprachlich ziemlich umständlich sind - kann ich mir auch besser merken als "Fremdworte", deren Erklärung ich mir dann auch wieder merken muss...
Außerdem würde doch durch eine Priority Queue die Laufzeit besser als [mm] O(n^2), [/mm] und wie soll ich dann die Laufzeit [mm] O(n^2) [/mm] erklären?
Ich war mir nur z. B. nicht sicher, ob für die Knoten in der zweiten Menge die kürzesten Wege auch schon berechnet sind, aber dem ist nicht so, wie ich zum Glück an einem Beispiel festgestellt habe. Und ich war mir anfangs auch nicht mehr sicher, ob der Knoten, dessen Nachfolger ich jetzt in die zweite Menge einfüge, dann schon direkt in die erste Menge geschoben wird. Aber ansonsten ginge das wohl auch nicht. Hätte ja sein können, dass da noch irgend so was ist, was ich nicht beachtet habe...
Viele Grüße
Bastiane
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 09:45 Fr 02.03.2007 | | Autor: | Frank05 |
> Hallo Frank!
>
> > Mit Floyd-Warshall kann man zB viel einfacher von allen
> > Knoten zu allen anderen die minimale Distanz berechnen (als
> > Nebeneffekt des Bildens der transitiven Hülle), was aber
> > natürlich eine deutlich schlechtere Komplexität hat.
>
> Ich will aber nur die Wege von einem Knoten zu allen
> anderen. Dafür mache ich es doch nicht so umständlich und
> berechne das für alle Knoten!
Wenn du alle kürzesten Wege von jedem Knoten zu jedem anderen Knoten hast, dann hast du selbstverständlich auch die kürzesten Wege von diesem einen Knoten zu allen anderen.
> > Und wenn der Graph einen Zyklus hat, dann fehlt hier und im
> > Satz vorher noch irgendwo eine Möglichkeit, damit das
> > Verfahren auch terminiert. So nehme ich immer wieder einen
> > Knoten und werfe immer wieder seine Nachfolger in die
> > zweite Menge um wieder weiterzumachen.
>
> Mmh, aber sobald für einen Knoten alle Nachfolger in die
> Menge geworfen wurden, wird der Knoten doch in die erste
> Menge rübergeschoben und somit nie wieder betrachtet!?
Betrachte wie gesagt einen Graph mit einem Zyklus. Am einfachsten sieht man es an einem Graph mit 2 Knoten, die Kanten in beiden Richtungen besitzen. Du fängst beim ersten Knoten an und fügst den zweiten in die Menge der Nachbarn, dann nimmst du diesen aus der Menge und wirfst den ersten wieder in die Menge der Nachbarn. Und dann gehts wieder von vorne los. Dir fehlt also immer noch das Abbruchkriterium.
> Ich war mir nur z. B. nicht sicher, ob für die Knoten in
> der zweiten Menge die kürzesten Wege auch schon berechnet
> sind, aber dem ist nicht so, wie ich zum Glück an einem
> Beispiel festgestellt habe.
In gewisser Weise schon. Wenn du diese Knoten einfügst, dann ausgehend von einem Knoten, dessen kürzester Weg bereits bekannt ist, so dass du zu diesem Weg die Länge der zusätzlichen Kante addieren kannst. Genau diese Gesamtlänge verwendest du ja dann eigentlich um den richtigen Knoten aus der zweiten Menge auszuwählen. Ich denke diesen Auswahlprozess solltest du noch etwas genauer ansehen auch im Hinblick auf die Terminierung.
> Und ich war mir anfangs auch
> nicht mehr sicher, ob der Knoten, dessen Nachfolger ich
> jetzt in die zweite Menge einfüge, dann schon direkt in die
> erste Menge geschoben wird. Aber ansonsten ginge das wohl
> auch nicht. Hätte ja sein können, dass da noch irgend so
> was ist, was ich nicht beachtet habe...
Wenn man diesen Knoten immer direkt in die erste Menge schieben würde, dann wäre a) die zweite Menge unnötig und b) man würde nur eine normale Tiefen- oder Breitensuche durchführen und damit nur die Existenz eines Weges von A nac h B feststellen.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 12:54 Fr 02.03.2007 | | Autor: | Bastiane |
Hallo Frank!
> > Ich will aber nur die Wege von einem Knoten zu allen
> > anderen. Dafür mache ich es doch nicht so umständlich und
> > berechne das für alle Knoten!
>
> Wenn du alle kürzesten Wege von jedem Knoten zu jedem
> anderen Knoten hast, dann hast du selbstverständlich auch
> die kürzesten Wege von diesem einen Knoten zu allen
> anderen.
Aber ich mache mir doch nicht mehr Arbeit, um mehr zu berechnen, als ich eigentlich haben will... ![[kopfschuettel]](/images/smileys/kopfschuettel.gif "[kopfschuettel]")
> > Mmh, aber sobald für einen Knoten alle Nachfolger in die
> > Menge geworfen wurden, wird der Knoten doch in die erste
> > Menge rübergeschoben und somit nie wieder betrachtet!?
>
> Betrachte wie gesagt einen Graph mit einem Zyklus. Am
> einfachsten sieht man es an einem Graph mit 2 Knoten, die
> Kanten in beiden Richtungen besitzen. Du fängst beim ersten
> Knoten an und fügst den zweiten in die Menge der Nachbarn,
> dann nimmst du diesen aus der Menge und wirfst den ersten
> wieder in die Menge der Nachbarn. Und dann gehts wieder von
> vorne los. Dir fehlt also immer noch das Abbruchkriterium.
Wenn ich doch aber sage, dass Knoten in der ersten Menge fertig abgearbeitet sind, dann ist doch klar, dass ich aus dieser Menge keinen Knoten mehr rausnehme. Und damit habe ich doch ein Abbruchkriterium!
> > Ich war mir nur z. B. nicht sicher, ob für die Knoten in
> > der zweiten Menge die kürzesten Wege auch schon berechnet
> > sind, aber dem ist nicht so, wie ich zum Glück an einem
> > Beispiel festgestellt habe.
>
> In gewisser Weise schon. Wenn du diese Knoten einfügst,
> dann ausgehend von einem Knoten, dessen kürzester Weg
> bereits bekannt ist, so dass du zu diesem Weg die Länge der
> zusätzlichen Kante addieren kannst. Genau diese Gesamtlänge
> verwendest du ja dann eigentlich um den richtigen Knoten
> aus der zweiten Menge auszuwählen. Ich denke diesen
> Auswahlprozess solltest du noch etwas genauer ansehen auch
> im Hinblick auf die Terminierung.
Und was ist mit diesem Beispiel hier?
[Dateianhang nicht öffentlich]
Die grünen Knoten sind immer die Knoten in der zweiten Menge. Als der Knoten rechts in diese Menge eingefügt wird, hat der Weg dorthin Länge 4, später wird dieser aber noch verkürzt!?!
> > Und ich war mir anfangs auch
> > nicht mehr sicher, ob der Knoten, dessen Nachfolger ich
> > jetzt in die zweite Menge einfüge, dann schon direkt in die
> > erste Menge geschoben wird. Aber ansonsten ginge das wohl
> > auch nicht. Hätte ja sein können, dass da noch irgend so
> > was ist, was ich nicht beachtet habe...
>
> Wenn man diesen Knoten immer direkt in die erste Menge
> schieben würde, dann wäre a) die zweite Menge unnötig und
> b) man würde nur eine normale Tiefen- oder Breitensuche
> durchführen und damit nur die Existenz eines Weges von A
> nac h B feststellen.
Da hast du mich glaube ich falsch verstanden. Der Knoten wird doch direkt in die erste Menge übernommen!
Viele Grüße
Bastiane
Dateianhänge:
Anhang Nr. 1 (Typ: png) [nicht öffentlich]
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 17:48 So 04.03.2007 | | Autor: | Frank05 |
> Wenn ich doch aber sage, dass Knoten in der ersten Menge
> fertig abgearbeitet sind, dann ist doch klar, dass ich aus
> dieser Menge keinen Knoten mehr rausnehme. Und damit habe
> ich doch ein Abbruchkriterium!
> Da hast du mich glaube ich falsch verstanden. Der Knoten
> wird doch direkt in die erste Menge übernommen!
Ich glaube wir reden hier eh nur aneinander vorbei. In deiner Beschreibung ist einfach nicht rausgekommen, dass ein Knoten, der in der ersten Menge ist auch nicht mehr aus der zweiten Menge genommen werden kann, falls er dort ebenfalls enthalten ist. Solange du unabhängig von der ersten Menge immer Knoten aus der zweiten Menge nimmst und wieder neu reingibst hilft dir die erste Menge natürlich nicht als Abbruchkriterium. Ich denke auch, dass dir das klar ist, aber in der Beschreibung hab ich es eben nicht gefunden.
|
|
|
|
