Klassifizierung von Kürzeste-Wege-Algorithmen

Moderator: Effiziente Graphenalgorithmen

yourmaninamsterdam
Nerd
Nerd
Beiträge: 681
Registriert: 26. Okt 2006 14:04
Kontaktdaten:

Klassifizierung von Kürzeste-Wege-Algorithmen

Beitrag von yourmaninamsterdam »

Hallo,

ich blicke in den Folien nicht so ganz durch die Klassifizierung. Verstehe ich das wie folgt richtig?

Label Setting
+ Single-Source-Multiple-Target
++ Dijkstra

Label Correcting
+ Single-Source-Multiple-Target
++ Bellman-Ford

+ All-Pairs
++ Floyd-Warshall (Dynamic Programming?)

Hybrid
+ All Pairs
++ Johnston

Benutzeravatar
mantra
Computerversteher
Computerversteher
Beiträge: 385
Registriert: 23. Okt 2005 23:56
Wohnort: Wiesbaden

Re: Klassifizierung von Kürzeste-Wege-Algorithmen

Beitrag von mantra »

Ich würde sagen, dass das eher zu "Effiziente Graphenalgorithmen" gehört.

Aber bis auf den hybriden Fall kann ich sagen, dass du das richtig eingeordnet hast ;) Doch ich kenne die Folien nicht, auf die du dich beziehst. Vielleicht sollte man das hier verschieben ;)

yourmaninamsterdam
Nerd
Nerd
Beiträge: 681
Registriert: 26. Okt 2006 14:04
Kontaktdaten:

Re: Klassifizierung von Kürzeste-Wege-Algorithmen

Beitrag von yourmaninamsterdam »

Hups, verzeihung, ich bin im falschen Forum gelandet...

Benutzeravatar
tiwoc
Ehemalige Fachschaftler
Beiträge: 475
Registriert: 21. Okt 2005 14:25
Kontaktdaten:

Re: Klassifizierung von Kürzeste-Wege-Algorithmen

Beitrag von tiwoc »

verschoben

Benutzeravatar
Stille
Moderator
Moderator
Beiträge: 195
Registriert: 3. Jul 2008 10:11

Re: Klassifizierung von Kürzeste-Wege-Algorithmen

Beitrag von Stille »

Hallo,

korrekt, denn:
yourmaninamsterdam hat geschrieben: Label Setting
+ Single-Source-Multiple-Target
++ Dijkstra
In jeder Iteration wird ein Knoten permanent gelabelt. Dieses Label repräsentiert die Kürzeste-Wege-Distanz, daher "Label Setting" (vgl. Folie 109). Daher kann die Suche auch abgebrochen werden, sobald der Zielknoten (im Falle von s-t-Wegen) permanent gelabelt wurde ("Early Termination").
Label Correcting
+ Single-Source-Multiple-Target
++ Bellman-Ford

+ All-Pairs
++ Floyd-Warshall (Dynamic Programming?)
Die Distanzlabels/-matrix können bis zum Schluß korrigiert werden, erst am Ende des Algorithmus repräsentieren sie Kürzeste-Wege-Distanzen, daher "Label Correcting".
Hybrid
+ All Pairs
++ Johnston
Klar, da Bellman-Ford und Dijkstra verwendet werden.
Wolfgang Stille
UKP Lab - FB Informatik
http://www.ukp.informatik.tu-darmstadt.de

yourmaninamsterdam
Nerd
Nerd
Beiträge: 681
Registriert: 26. Okt 2006 14:04
Kontaktdaten:

Re: Klassifizierung von Kürzeste-Wege-Algorithmen

Beitrag von yourmaninamsterdam »

Ist der Floyd-Warshall-Algorithmus auch der Dynamic-Programming-Repräsentant?

Benutzeravatar
Stille
Moderator
Moderator
Beiträge: 195
Registriert: 3. Jul 2008 10:11

Re: Klassifizierung von Kürzeste-Wege-Algorithmen

Beitrag von Stille »

Ja, die Rekursionsformel ist ja quasi 1:1 iterativ umgesetzt.
Wolfgang Stille
UKP Lab - FB Informatik
http://www.ukp.informatik.tu-darmstadt.de

Antworten

Zurück zu „Effiziente Graphenalgorithmen“