# Dijkstra's Algorithm

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

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

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.
• 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. – Bob Jan 2 '17 at 16:16