---
tags: fall 2018 cs61b
---
# Dijkstra's Algorithm
[TOC]

## Introduction
Given a graph, Dijkstra's Algorithm allows us to find the **shortest path** from an **arbitrary start node** to **every other node** or **an arbitrary goal node**.

Similar to how BFS and DFS use a queue and stack, respectively, Dijkstra's Algorithm uses a **priority queue** to process each node in our graph. We use a priority queue because at each step, we want to pop and process the node with the **smallest distance** from the start node. We have to assign each node in the priority queue a *priority* based off the
known smallest distance of the node from the start node. Nodes with the smaller distances will have higher priority and be popped first.

*Note:* Dijkstra's Algorithm only works with non-negative weight edges.

There are multiple methods to keep track of the nodes we've processed so far. Let's run Dijkstra's Algorithm from node $S$ to $G$.

For each $v$ we process, we calculate its distance from $S$. Nodes that are not processed yet have a distance of $\infty$. We then pop off the $v$ with the smallest distance and update the distance of its neighbors from $S$ with its smallest possible distance from $S$.

| v | Init | Pop S | Pop A | Pop B | Pop C | Pop D | Pop G|
|:------: |:-----------: | :-----------: | :-----------: | :-----------: |:-----------: | :-----------: | :-----------: |
| S | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| A | $\infty$ | 1 | 1 | 1 | 1 | 1 | 1 |
| B | $\infty$ | $\infty$ | 2 | 2 | 2 | 2 | 2 |
| C | $\infty$ |$\infty$ |$\infty$ | 3 | 3 | 3 | 3 |
| D | $\infty$ | $\infty$| 4 | 4 | 4 | 4 | 4 |
| E | $\infty$ | $\infty$| 9 | 9 | 9 | 9 | 9 |
| G | $\infty$ |$\infty$ | $\infty$ | $\infty$| $\infty$| 6 | 6 |

Based on the nodes we popped, the shortest path would be **S-A-D-G**.

## Runtime Analysis
### Context
While DFS and BFS rely on stacks and queues respectively, Dijkstra's algorithm relies on a **priority queue** to return nodes that can be reached with the **shortest path possible**. We know from lab that **priority queues are implemented using heaps** and that the priority queue for Dijkstra's algorithm will be specifically relying on a **min heap**.

### Breaking it Down
Dijkstra's algorithm can be broken down into three steps when you look at each node in the graph:
1. **Insert the Node:** Insert the node into the priority queue (insert into a min heap).
2. **Remove minimum node:** Pop off the node with the highest priority from the priority queue (remove root node in the min heap and re-heapify).
3. **Update priority:** Consider the edges weights of the neighboring nodes of the node you just popped off and update the priorities in the priority queue accordingly. (Bubble the nodes in the min heap according to priority)

:::info
**Important Note:**
Think of the runtime from a higher, more conceptual perspective instead of from the perspective of your lab code. It's easy and quite common to get bogged down with details of the lab implementation and be skeptical with this analysis.

This may look like a different implementation than the algorithm you wrote in lab. Most notably, we are looking at the edge weights of neighboring nodes and **updating the priorities** in the heap **instead of inserting a new node to our heap with a new priority**.
:::

### Worst Case Runtime Analysis
Let's denote the number of our vertices as $V$ and number of our edges as $E$.

1. **Insertion:** $Θ(V \textrm{ log } V)$
We will end up inserting all of our vertices into our heap, so we will make $V$ **function calls** for insertion. An insertion into our heap will take $O(\textrm { log } V)$ because we need to bubble up the node to the correct spot. Since we do a **heap insertion for every vertex**, the worst case runtime for inserting every vertex is $\Theta(\textrm { log } V)$.
2. **Remove Minimum Node:** $Θ(V \textrm { log }V)$
Since the worst case mentions that we put all of our vertices our priority queue, we know we will make $V$ **function calls** to remove the minimum node from the heap. Removing the minimum node in the heap will take $O(\textrm { log } V)$ because we need to replace the root node with a node from the end and bubble it down. The worst runtime of removing the minimum node for every vertex is $Θ(V \textrm { log } V)$.
3. **Update Priority:** $Θ(E \textrm { log } V)$
We update the priorites based off the edge weights from the current vertex we popped off to its neighboring vertices. Therefore, we will make $E$ **function calls**. Updating the priority of a vertex in the priority queue is equivalent to bubbling a node in a heap to the correct spot, so the runtime of updating the priority of one vertex is $O(\textrm{ log } V)$. Since we are updating the priority every time we look at an edge, the overall runtime of update priority is $\Theta(E \textrm{ log } V)$.

Since each step occurs one after the other, we can add up the runtime of every step to get the final runtime.

**Worst Case Runtime:** $\Theta(V \textrm{ log }V + E \textrm{ log }V)$
If $E > V$ (a complete graph), then the runtime can be further simplified to $Θ(E \textrm { log }V)$.

## Resources
[Dijkstra's Algorithm Visualizer](https://www.cs.usfca.edu/~galles/visualization/Dijkstra.html)