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
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.