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.
Dijkstra's shortest path algorithm was taught as a topic during my degree of engineering.But at that time it was not clear to me.But now I know ot well.Thanks
ReplyDelete