0
$\begingroup$

I have recently implemented Dijkstra's Algorithm to the shortest path between all pairs of nodes in the graph. I have implemented this code in Java. As instructed I am using a linked list to represent the adjacency matrix. As instructed, I am running my algorithm for a complete graph. The running time for a 1000 node complete graph is about 361 minutes. For 2000 nodes, my program has been running for close to a day, and it is still running.

I would like to run this for a complete graph of 6000 nodes but the running time is going to be too long. I am wondering, if this is too be expected.

Bob

$\endgroup$
  • 2
    $\begingroup$ I think your question could be more fruitfully answered on stackoverflow where you could post your code and get feedback on implementation details. $\endgroup$ – adrianN Jan 2 '17 at 16:19
2
$\begingroup$

Dijkstra has running time $\mathcal{T}(G) \in \Theta(|E| + |V| \log |V|)$. If the graph is dense then $|E| \in \Theta(|V|^2)$, which means that $\mathcal{T}(G) \in \Theta(|V|^2)$.

A quadratic running time means that a graph with twice as much nodes will take four times as much time to be processed. If $1000$ nodes required $6$ hours, then it is not surprising that $2000$ nodes will take about one day.

As you know, constants depend on the machine you're running your code on, it is therefore impossible to judge the speed of your code having the clock running time as the only datum; however your times strike me as particularly high for a reasonably modern personal computer, I would expect them to be a couple of orders of magnitude lower.

$\endgroup$
  • $\begingroup$ I think that your answer is off by a factor of $|V|$ because I am doing it for all pairs of nodes. The standard Dijkstra algorithm solves the problem for a single source node. Please comment. $\endgroup$ – Bob Jan 2 '17 at 16:16
  • 3
    $\begingroup$ Then Dijkstra is not a good solution. Use an all-pairs shortest path algorithm instead, such as Floyd-Warshall. $\endgroup$ – quicksort Jan 2 '17 at 16:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.