Learn Dijkstra's Algorithm by implementing it with Python!

Dijkstra's Algorithm: Python

Let's finish the algorithm!

First, we'll traverse the `vertices_to_explore` heap until it is empty, popping off the vertex with the minimum distance from `start`. Inside our `while` loop, we'll iterate over the neighboring vertices of `current_vertex` and add each neighbor (and its distance from `start`) to the `vertices_to_explore` min-heap.

In each `neighbor` iteration, we will do the following:
- Identify `neighbor`'s distance from `start`.
- Make sure the new distance found for `neighbor` is less than the distance currently set for `distances[neighbor]`.
- Update `distances[neighbor]` if the **new distance** is smaller than the currently recorded distance.
- Add `neighbor` and its distance to the `vertices_to_explore` min-heap.

Finishing the Algorithm!

Remember that Dijkstra's Algorithm works like the following:

1. Instantiate a dictionary that will eventually map vertices to their distance from their start vertex
- Assign the start vertex a distance of 0 in a min heap
- Assign every other vertex a distance of infinity in a min heap
- Remove the vertex with the smallest distance from the min heap and set that to the current vertex
- For the current vertex, consider all of it’s adjacent vertices and calculate the distance to them by **(distance to the current vertex) + (edge weight of current vertex to adjacent vertex)**. If this new distance is less than its current distance, replace the distance.
- Repeat 4 and 5 until the heap is empty
- After the heap is empty, return the distances


In order to keep track of all the distances for Dijkstra's Algorithm, we will be using a heap! Using a heap will allow removing the minimum from the heap to be efficient. In `python`, there is a library called `heapq` which we will use to do all of our dirty work for us!

The `heapq` method has two critical methods we will use in Dijkstra's Algorithm: `heappush` and `heappop`.
- `heappush` will add a value to the heap and adjust the heap accordingly
- `heappop` will remove and return the smallest value from the heap

Let's say we start by initializing a heap with the following tuple inside:
```py
heap = [(0, 'A')]
```
We can add values to this heap like this:

```py
heapq.heappush(heap, (1, 'B'))
heapq.heappush(heap, (-4, 'C'))
```

We can remove the smallest value in the heap like this:

```py
value, letter  = heapq.heappop(heap)
```

`value` will be equal to `-4`, and `letter` will be equal to `'C'`. 


You can read more about the documentation of `heapq` [here](https://docs.python.org/3/library/heapq.html).


Understanding Heapq

Nice work implementing Dijkstra's algorithm in Python!

Feel free to play around with the code in the code editor. 

What do you think the distances returned would look like if your starting point were different?

Dijkstra's Algorithm in Python: Review

Now, let's start writing the algorithm!

The first part of the algorithm is all about initialization! Here's what we have to do:

- Define the function with a `start` vertex and a graph.
- Instantiate a `distances` dictionary that will eventually map vertices to their distance from their start vertex.
- Assign the start vertex a distance of `0`.
- Assign every other vertex a distance of `infinity`.
- Set up a `vertices_to_explore` min-heap list that keeps track of neighboring vertices left to explore.

After initializing these variables, we can then traverse the graph and update the distances!

Initializing Dijkstra's Algorithm

Before we delve into implementing Dijkstra's Algorithm, we need a graph to explore it, but how exactly do we represent graphs in python? One of the ways to represent graph is through an adjacency list using a Python dictionary. 

Take a look at the following graph represented by an adjacency list:
```py
graph = {
  'A': [('B', 10), ('C', 3)],
  'B': [('C', 3), ('D', 2)],
  'C': [('D', 2)],
  'D': [('E', 10)],
  'E': [('B', 15)],
}
```
Reading this adjacency list, we can tell the `graph` has 5 vertices: `'A', 'B', 'C', 'D', 'E'`.

There is a path from `'A'` to `'B'` with a cost (or edge weight) of `10` and a path from `'A'` to `'C'` with a cost of `3`.

There is a path from `'B'` to `'C'` with a cost of `3` and a path from `'B'` to `'D'` with a cost of 2.

There is a path from `'C'` to `'D'` with a cost of `2`.

There is a path from `'D'` to `'E'` with a cost of `10`.

There is a path from `'E'` to `'B'` with a cost of `15`.