hello, I wrote a program that works on a graph containing 36692 nodes.The program should find all the shortest path in a graph between each pair of nodes. the graph is undirected and unweighted and sparse. I can not use floyd-warshall algorithm because the complexity of it is o(v^3). so, I used Dijkstra and repeat it |v| times, so the complexity is o(VE+V^2LOGV).since graph is sparse (|E|
thank you for your useful answer. my computer just has a core(TM)i3-2100 CPU. Does the implementation of the article(All-Pairs Shortest-Paths for Large Graphs on the GPU) on my computer reduces the run time? is it helpful to implement it on my computer or I should think about another solution?
Best,
Maryam Kiabod
Since you say that "the graph is undirected and unweighted and sparse", you might simply run a BFS from every node. Not only is the asymptotic running time O(|E||V|) but it is also really simple. So I suppose that perhaps your graph is weighted: In such case, there are (asymptotically) faster algorithms than the one you're using, but I am not sure how practical they are.
In any case, if you have access to it, you might want to look up "All Pairs Shortest Paths in Sparse Graphs" in Encyclopedia of Algorithms:
http://www.springer.com/us/book/9780387301624
Given that your network is unweighted, depending on the network topology you may be better of using Breth First search (BFS).
In your case, Dijkstra is slower because you have to sort your pending edges each time.
What programming language are you using? Python as pretty good data structures for this kind of task.
See this for a simple implementation : http://eddmann.com/posts/depth-first-search-and-breadth-first-search-in-python/
- Badges
- Science topic
- Similar topics
- Computer Science and Engineering
- Algorithms