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

*1 point*

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