Shortest Path Berechnung (Nur Topologie)

[Eggcake]

Im Rahmen meiner Masterarbeit muss ich in einem Netzwerk kürzeste Pfade berechnen. Wichtig dabei ist, dass es nur um die Topologie geht. Ich verwende einen dualen Graphen, wo ein Node im Prinzip eine Strasse darstellt und die Edges die Verbindungen, welche diese Strasse zu anderen Strassen (d.h. Nodes) aufweist. Da die "Strassen" an sich aus mehreren Segmenten bestehen, kann ich nicht direkt ein Distanzmass verwenden (wie weit entfernt ist eine "Strasse" von einer anderen "Strasse", welche mit dieser verbunden ist? Direkt daneben? Mittelpkt zu Mittelpkt?) bzw. es macht meiner Meinung nach wenig Sinn. Primär bin ich erstmals auch nur an der Topologie interessiert. Der Graph ist also ungewichtet (Edges haben Weight von 1, Nodes zunächst ebenfalls 0).

-----
Kleine Nebeninfo:

Ich habe zwei Datensätze - einer hat rund 4'500 Segmente, der andere 130'000. Aus den Segmenten erstelle ich mit einem Algorithmus Strassen (grundsätzlich ist dieser sehr banal bzw. hängt zunächst einfach diejenigen Segmente zusammen, welche den kleinsten Winkel zueinander haben bis zu einem threshold). Aus diesen zusammenhängenden Strassen mache ich dann den dualen Graphen.

Das alles geht eigentlich sehr schnell. Beim kleinen Datensatz brauche ich insgesamt rund 150ms, beim grossen ~4s für den Graphen, 1.5s für die Strassen, ~500ms für den dualen Graphen.
-----

Ich muss im Graphen für ALLE Nodes, ALLE kürzesten Pfade zu allen anderen Nodes berechnen. Die beste Option stellte eigentlich nur der Dijkstra Algorithmus mit einem Fibonacci Heap dar. Algorithmen, welche eine gewisse Heuristik verwenden (A* z.B.) gehen meinem Empfinden nach nicht, da ich nicht wüsste welche Heuristik ich bei einem ungewichteten Graphen verwenden soll und ebenso keine direkten Distanzmasse verfügbar sind (eventuell hat jemand ja eine Idee).


Wie dem auch sei: das Problem ist, dass ich für den kleinen Datensatz, welcher im dualen Graphen ~1500 Nodes und ~3000 Edges aufweist rund 1 Sekunde benötige, für den grossen, welcher ~37'000 Nodes und ~70'000 Edges aufweist jedoch 30min benötige, was IMHO ein etwas grosser Anstieg ist (eigtl. sollte es log(Nodes) * Nodes + Edges sein). Anstatt einem Fibonacciheap habe ich's auch mit einer normalen PriorityQueue versucht - doch da stieg die Laufzeit um das 200fache an :>


Die eigentliche Frage:
Kennt jemand einen Algorithmus, welcher eine bessere Laufzeit als Dijkstra mit Fibonacci Heap aufweist und welcher auch funktioniert, wenn man keine Heuristik verwenden kann?


Alternativ könnte natürlich auch mein Code einen Fehler aufweisen - habe allerdings noch nichts gefunden..


TLDR: Fettgedrucktes lesen

[RLZ]

Ich muss im Graphen für ALLE Nodes, ALLE kürzesten Pfade zu allen anderen Nodes berechnen. Die beste Option stellte eigentlich nur der Dijkstra Algorithmus mit einem Fibonacci Heap dar.
Jetzt nur rein von der Theorie her:
Du willst ein "All-pairs shortest path" Algorithmus.
Du nimmst dafür aber Dijkstra, was ein "Single-source shortest path" Algorithmus ist. Klar lässt sich ein SSSP dafür verwenden, aber effizient ist anders. Ich würde bei der Suche mal mit Floyd-Warshall anfangen und erstmal schauen, ob es nicht ein Lib gibt, die eine optimierte Implementierung für das Problem hat (e.g. für C++ bietet Boost sowas an).

[universaL]

Wie dem auch sei: das Problem ist, dass ich für den kleinen Datensatz, welcher im dualen Graphen ~1500 Nodes und ~3000 Edges aufweist rund 1 Sekunde benötige, für den grossen, welcher ~37'000 Nodes und ~70'000 Edges aufweist jedoch 30min benötige, was IMHO ein etwas grosser Anstieg ist (eigtl. sollte es log(Nodes) * Nodes + Edges sein). Anstatt einem Fibonacciheap habe ich's auch mit einer normalen PriorityQueue versucht - doch da stieg die Laufzeit um das 200fache an :>


Deine Laufzeiteinschätzung gilt ja nur für die Kürzesten Pfade eines Knoten zu allen anderen, du willst ja aber von allen zu allen ;) Also rufst du den Algorithmus 37000/1500 =~ 25 öfter auf, was ungefähr mit deinen zeiten hinkommt, wenn ich das grade richtig sehe ;)

Aber wie schon erwähnt sölltest du dir Floyd-Warshall angucken. http://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm#Implementations listet einige Implementationen auf ;)

[Eggcake]

Vergessen zu erwähnen:
Ich muss auch die Pfade selber kennen - afaik liefert dies Floyd-Warshall nicht. Hintergrund ist, dass Nodes (Strassen), welche für den Shortest Path zwischen anderen Strassen "verwendet" werden dann für einen nächsten Schritt höher gewichtet werden sollen - also muss ich wissen, welche Strassen benutzt werden.

@Universal
Also entweder ich verstehe etwas falsch, aber es ist 1 Sekunde vs. 30 Minuten, was nicht ganz dem Faktor 25 entspricht :)
Aber ja, die Laufzeit dürfte eh nicht so berechnet werden können, da ich ja den Durchgang nicht abbreche, wenn ich beim Target angekommen bin sondern immer den gesamten Datensatz durchrechne.

Edit2:
Die Frage ist auch, ob mein FibonacciHeap gut ist. Ich habe ihn vom Graphmaker-Projekt entnommen, nachdem ich diesen Blogeintrag (http://cafenate.wordpress.com/2008/05/31/analysis-of-java-implementations-of-fibonacci-heap/) gelesen hatte (ich programmiere mit Java). Ich habe 3 durchgetestet, wobei einer davon halb so schnell ist wie die anderen beiden...

[Gast]

Du könntest dir auch Fast Marching ("Verallgemeinerung" von Dijkstra) ansehen, ist zwar eine kontinuierliche Methode kann man aber auch auf deinen diskreten Fall anwenden. Wenn ich dein Problem richtig verstanden habe solltest du mit Fast Marching in einem Rutsch den kürzesten Pfad von jedem Punkt zu jedem anderen bekommen, musst also nur einmal rechnen.

[DocEW]

Muss zugeben, dass ich jetzt nicht alles gelesen habe, aber hast du mal A* [wiki] (http://de.wikipedia.org/wiki/A*-Algorithmus) angeschaut?

[Trap]

Vergessen zu erwähnen:
Ich muss auch die Pfade selber kennen - afaik liefert dies Floyd-Warshall nicht.
Die kann man aus der Distanzmatrix rekonstruieren. Bei Kantengewicht überall 1 sogar primitiv einfach: Jeder Nachbar mit Zielentfernung um 1 kleiner als die des aktuellen Knoten liegt auf einem kürzesten Pfad zum Ziel.

Außerdem kann man mit der Methode auch alle kürzesten Pfade aufzählen, falls einen das interessiert.
Hintergrund ist, dass Nodes (Strassen), welche für den Shortest Path zwischen anderen Strassen "verwendet" werden dann für einen nächsten Schritt höher gewichtet werden sollen - also muss ich wissen, welche Strassen benutzt werden.
Willst du im Endeffekt ein Flussproblem auf dem Graphen lösen?

[Eggcake]

@Gast: danke, schaue ich mir auch an.
@doc: A* schließe ich aus, da ich nach meiner Überlegung keine solide Heuristik erstellen kann.

@trap
Ich schau mir das morgen nochmals genauer an, danke (habe zz floyd nur kurz wiki gelesen und da stand afaik, dass man die pfade nicht rekonstruieren könne).
Bei der Arbeit geht es um die automatische Selektion von Strassen bei einer Massstabsverkleinerung. Und eine Methode die ich verwende basiert auf diversen Zentralitätsmassen des Graphen des Strassennetzes (Grad, Closeness, Betweenness,... ). Für die Betweenness benötige ich den Pfad selber.

Edit: Floyd sollte passen, ich implememtiere das morgen mal und berichte.

[RLZ]

habe zz floyd nur kurz wiki gelesen und da stand afaik, dass man die pfade nicht rekonstruieren könne
Da steht sogar ein Pseudoalgorithmus (https://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm#Path_reconstruction)dabei. ;)

[Eggcake]

Gibt wohl noch bessere Algorithmen für Sparse Graphs sehe ich gerade, ich werde das, wie gesagt, morgen mal angehen. Besser als Dijkstra dürfte es auf jeden Fall sein ;)

Edit: Also nur mal so als Info: Laut diversen Quellen ist der Johnson's algorithmus bei sparse graphs (was bei meinem Graphen zutrifft) schneller als der Floyd-Warshall Algorithmus - und im Prinzip ist es, im Falle von einem nicht gerichteten Graphen mit positiven Gewichten genau der Djikstra-Algorithmus, angewendet auf alle Nodes. Bin gerade etwas am zweifeln ob der Floyd-Warshall wirklich schneller ist, aber in ein paar Stunden bin ich schlauer :)

[Eggcake]

So, meine bisherigen Erkenntnisse:

Gründe wieso Floyd-Warshall unsinnig ist - sofern ich alles richtig verstanden habe ;) :

1. Space complexity von N²: Für die einfache Shortest Path Berechnung ohne Path reconstruction benötige ich bereits 37'000*37'000 Integer für die Distanzmatrix, was etwa 5GB entspricht: viel zu viel. Mit Path reconstruction käme nochmals eine N*N Matrix hinzu, wo wir bei über 10GB wären.

2. Time complexity von N³: Im Wiki Beitrag ist ein weiterer Algorithmus (Johnson's (http://en.wikipedia.org/wiki/Johnson%27s_algorithm)) verlinkt, welcher bei Sparse Graph schneller sein soll. Und mein Graph ist definitiv "sparse", mit einem 1:2 Node:Edge-Verhältnis. Und siehe da, aus was besteht der Johnson's Algorithmus? Lässt man die Umwandlung weg, welche nur für gerichtete Graphen mit negativen Gewichten notwenig ist, besteht dieser Algorithmus genau aus N Aufrufen des Djikstra Algorithmus, wo wir bei einer Time complexity von N² x log(N) + N x E wären (nicht wie von mir fälschlicherweise oben behauptet, da ich ja eben N Aufrufe habe). Wenn ich hier nur mal so testhalber Werte von meinem Graphen eingebe und mit Floyd-Warshall vergleiche, so besteht ein Unterschied von 3 Grössenordnungen, d.h. Floyd-Warshal dürfte 1000x langsamer sein. Kann sein, dass ich Käse gerechnet habe, aber er dürfte definitiv langsamer sein.


Floyd-Warshall kam also aus diesen Gründen nicht in Frage und es scheint so, dass ich mit Djikstra sowieso bereits den schnelleren Algorithmus ausgewählt habe...

Ich bin schliesslich auf Brande's Algorithmus (http://www.cs.ucc.ie/~rb4/resources/Brandes.pdf) gestossen, welcher spezifisch auf mein Problem gerichtet entwickelt wurde. Zeitkomplexität sollte der Theorie nach bei N x E liegen und Platzkomplexität bei N + E. Naja schliesslich bin ich nun etwa 30-50% schneller mit Brande's Algo als mit Djikstra - immerhin...mittlerweile habe ich aber glaube ich auch genug davon, gibt schlimmeres als bisschen Wartezeit. Ansonsten setze ich eben noch Multithreading ein (geht eigentlich mit Djikstra und Beardes sehr banal).


Danke euch für die Inputs, werde aber das Problem wohl erstmal ruhen lassen, da ich mit der Laufzeit wohl leben kann... :)

[RLZ]

Hm...
Das kommt mir nun seltsam vor, dass es da nichts schnelleres geben soll. Immerhin lassen sich ja alle Teilpfade eines Pfades schon direkt als Ergebnis wiederverwenden und müssen nicht mehr neu berechnet werden. Damit sollte sich die Matrix recht schnell füllen.

Aber theoretische Informatik nun auch wirklich nicht mein Ding. ;)

[Eggcake]

Mein's eigentlich auch nicht :ugly:

Naja, man findet schon ziemlich viele Paper und Artikel zum Thema Centrality, insbesondere Betweenness...das "schöne" daran ist ja, dass man's einfach parallelisieren kann (da gibt's auch etliche Paper dazu)...aber irgendwo ist auch mal Schluss :>
Passt jetzt schon, hat mich eben nur auch etwas verwundert, dass man bei Brande wohl schon langsam am Ende der Fahnenstange ist. Auf der anderen Seite...mindestens 37'000 kürzeste Pfade in 30ms berechnen ist ja auch nicht sooo schlecht :D

Edit: Hab's nun doch nicht lassen können und das Ganze parallelisiert. Mit 4 Kernen komme ich nun auf 7 Minuten von ursprünglich 60 Minuten (Dijkstra mit schlechtem Fibonacci Heap)...passt :)