Dijkstra's optimization for dense graph?
Is there any other way to calculate the shortest path for an almost complete graph other than Dijkstra? I have about 8000 nodes and about 18 million edges. I went through the a to b on map thread and decided to use Dijkstra. I wrote my script in Perl using the Boost :: Graph library. But the result is not what I expected. It took about 10+ minutes to compute one shortest path using the call $ graph-> dijkstra_shortest_path ($ start_node, $ end_node);
I understand that there are many edges and this could be the reason for the slow runtime. Am I dead in the water? Is there any other way to speed this up?
Short answer: Dijkstra is your best choice if you only want a few shortest paths, and the Floyd-Warshall algorithm is better if you want to find the shortest paths between each pair of nodes.
-
Dijkstra's algorithm finds the shortest paths from one source to all other nodes in the graph for weighted graphs. It works on dense graphs in O (V ^ 2) time.
-
Floyd-Warshall finds the shortest paths between all pairs of nodes. It requires tight representation and runs in O (V ^ 3) time. It works on weighted or unweighted charts.
Even though your graph is dense (as the title of your question is), there might be some benefit to converting it to a sparse graph and using a sparse Dijkstra implementation if you just want to find some shortest paths. Sparse Dijkstra works in O (E log V).
Note that this assumes that all of your draw weights are non-negative; if they are, then you cannot use any of them. You will have to use an even slower algorithm like Bellman-Ford.
source to share
You can also try to give the A * algorithm .
This approach is especially useful if you have access to good heuristics.
source to share