Ich habe etwa 70.000 Knoten und 250.000 Kanten, und der Graph ist nicht notwendigerweise verbunden. Offensichtlich ist die Verwendung eines effizienten Algorithmus entscheidend. Was empfehlen Sie?
Als Nebenbemerkung würde ich mich darüber freuen, wie Sie die Aufgabe auf mehrere Maschinen aufteilen können - ist das bei dieser Art von Problem sogar möglich?
Danke
Sie könnten den Floyd-Warshall-Algorithmus verwenden. Es löst genau dieses Problem.
Die Komplexität ist O (V ^ 3).
Es gibt auch Johnsons Algorithmus mit einer Komplexität von O (V ^ 2 * log V + VE). Letzteres ist auch leicht zu verteilen, weil es den Dijkstra-Algorithmus V-mal ausführt, der parallel ausgeführt werden kann.
MapReduce ist ein großartiger verteilter Algorithmus dafür, obwohl er vielleicht etwas zu leistungsstark ist. Wenn Sie daran interessiert sind, werfen Sie einen Blick auf diesen Vortrag oder vielleicht diesen Blogeintrag zur Inspiration. (In der Tat, als ich MapReduce unterrichtet wurde, war dies eines der ersten Beispiele.)
Für 250k-Kanten und 70k scheint der Graph relativ spärlich zu sein, Der Dijkstra-Algorithmus läuft in O( E + V log V ) für jeden Knoten, für eine vollständige Laufzeit (alle Quellen) von O( VE + V^2 log V ) . Das sollte schnell genug sein, aber die üblichen Vorbehalte gelten für Dijkstra's. (Negative Kanten.)
Sie können sich auch den Johnson-Algorithmus ansehen, wenn Ihr Problem mit negativen Gewichten, aber nicht mit negativen Zyklen arbeitet . Insbesondere kann es auch verteilt werden, da es den neu gewichteten Graphen verwendet und den Dijkstra-Algorithmus von jedem Knoten aus ausführt.
Es gibt zwei naive Wege, dieses Problem zu parallelisieren:
1) Identifizieren Sie Unterkomponenten und verteilen Sie diese über verschiedene Computer. Die Pfadlänge zwischen zwei Knoten aus zwei verschiedenen Komponenten ist nicht definiert.
2) Laden Sie das Diagramm auf verschiedenen Computern und geben Sie jedem Computer eine Liste von Knoten, um alle kürzesten Pfade zu berechnen. Die Ergebnisse für einen Knoten hängen nicht von den Ergebnissen eines anderen Knotens ab, sodass Sie dieses Problem parallelisieren können.
Upside: nicht zu schwer zu implementieren, aber ich würde es nur so machen, wenn Sie das einmal lösen müssen. Wenn dies ein wiederkehrendes Problem ist, sollten Sie sich den verteilten Algorithmus ansehen.
Benutze igraph , es ist in C geschrieben, ziemlich schnell und du kannst Python als Wrapper-Sprache benutzen.
Sehen Sie sich Artikel / Publikationen an, die folgende Schlüsselwörter haben: verteilte Graphensuchalgorithmen. Hier ist eine, die hilfreich sein kann.
Es gibt auch dieses ACM-Konto nur Papier: Verteilte Berechnung in Graphen: Algorithmen für den kürzesten Weg
Tags und Links algorithm graph-theory graph shortest-path