Hallo zusammen,
welche Algorithmen gibt es denn noch neben den üblichen verdächtigen um
kürzeste Wege in einem Graphen zu bekommen?
Gerne auch Optimierungsverfahren wie zum Beispiel
Will da einfach mal ein wenig experimentieren.
Gruß Mike
Moien
welche Algorithmen gibt es denn noch neben den üblichen
verdächtigen um
kürzeste Wege in einem Graphen zu bekommen?
Da fehlt ein üblicher Verdächtiger: flooding. Ist aus Sicht des Informatiker extrem gut verteilbar und sollte deshalb z.B. auf GPU gut laufen.
cu
Hallo zusammen,
welche Algorithmen gibt es denn noch neben den üblichen
verdächtigen um
kürzeste Wege in einem Graphen zu bekommen?
Hallo Mike,
es gibt noch Abwandlungen von Dijkstra.
Es wird z.B. mit Hierarchien gearbeitet:
(Nebenstraße, Hauptstr., Landstr, Autobahn)
Dadurch müssen nicht alle Kanten angeschaut werden,
es kommt allerdings nicht der kürzeste Weg heraus.
Ein hieraricher Algorithmus, der exakt ist, findet sich hier:
http://algo2.iti.uni-karlsruhe.de/schultes/hwy/esaHw…
Oder es werden geometrische Eigenschaften ausgenutzt:
ftp://ftp.math.tu-berlin.de/pub/Preprints/combi/Repo…
- Kruskal
Vorsicht, Kruskal ist für minimale Spannbäume!
Grüße
Thorsten