Dijkstra's shortest path, Computation

Comment 1:

How to derive the Dijkstra’s shortest path algorithm’s estimated running time?

Follow-up:

As an approximation, we note that each link needs to be visited at once. In the worst case, we can have on the order of (n x n) links, where n is the number of nodes in the graph. Thus, the estimated running time is approximately (n x n) steps.

Comment 3:

Maybe it is true that if we put in more computing/storage resources, we can solve just about any problem.

Follow-up:

If you attended Tutorial 3, you should have learned that there are really difficult problems, in the sense that you will need unreasonably large amount of storage (e.g., every atom in the universe) and computing power to solve. Furthermore, in Problem 3 of Tutorial 3, you will see that there are problems that are simply unsolvable.