Graphs: Dijkstra's Algorithm

What is a Greedy Algorithm?

"A greedy algorithm is an algorithmic paradigm that follows the problem solving heuristic of making the locally optimal choice at each stage with the intent of finding a global optimum. In many problems, a greedy strategy does not usually produce an optimal solution, but nonetheless a greedy heuristic may yield locally optimal solutions that approximate a globally optimal solution in a reasonable amount of time." - Wikipedia

Finding the Shortest Path Using Dijkstra's Algorithm

In certain cases, finding all the local optimals can lead to a globally optimal solution. One such greedy algorithm is Dijkstra's algorithm for finding the shortest path from a single source node. The following video describes the Dijkstra algorithm in great detail. It is presented in four parts:

  1. A mathematical explanation is given;
  2. The Big O complexity of the algorithm is described;
  3. A second explanation with hints on how to implement it in a computer program is provided;
  4. An explanation is provided regarding why the algorithm may fail if some of the costs are negative.
It is essential that you understand all four of these concepts.



1 point
What is the run time for Dijkstra's Algorithm? Hint: n = the number of nodes