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 AlgorithmIn 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:
- A mathematical explanation is given;
- The Big O complexity of the algorithm is described;
- A second explanation with hints on how to implement it in a computer program is provided;
- 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.
What is the run time for Dijkstra's Algorithm? Hint: n = the number of nodes