Context

2nd year CS
Know about Binary Trees
DFS & BFS
Know about Graphs
Know of Greedy Algorithms
Know about Queues
Know about Priority Queues (high level)
Know about Heaps
Using Python
Familiar with website delivery
- More notes than slides
- Discover ideas as opposed to throwing them at the students
- Interpreter
- Pencil & paper

Graphs¶

Graph: $G = (V, E)$ .

Vertices: $V = \{v_1, v_2, ... , v_n\}$ .

Edges: $E = \{e_1, e_2, ... e_m\}$ ,: where $e_i \in \{(a, b) | a, b \in V\}$

Example

$V = \{A, B, C, D\}$

$E = \{(A, B), (B, C), (A, C), (C, D)\}$

Implementation

Weighted Graphs

Each edge has a weight associated with it
More general

Airports

Road Networks (kinda’ to scale)

Problem: Route Planning¶

How do we get from point A to point J?
We want to minimize the sum of the edge weights on the path

Try every possible path? (Brute Force)

Activity

Find all paths from A to J.

A -> B -> D -> G -> J (length: 10)
A -> B -> D -> H -> J (length: 9)
A -> B -> D -> F -> H -> J (length: 7)
A -> C -> E -> F -> H -> J (length: 6)
A -> C -> E -> F -> H -> D -> G -> J (length: 17)
A -> C -> E -> F -> D -> G -> J (length: 11)
A -> C -> E -> F -> D -> H -> J (length: 10)

There are more, but these are the admissible ones

How would we implement this?

If we only needed 1 path, we could just do like a depth first search (DFS)
So let’s just keep doing a DFS until we exhaust all paths
Keep track of the paths, and in the end, pick the one with the smallest path

Simple, Lazy Greedy

OK, we know the above will work, but we end up having to do a lot of work…
When given choices, always pick the smallest?

A -> C -> E -> F -> D -> G -> J (length: 11)

Not the best, but we only had to look at 1 path though!

Let’s try on this example:

If we follow the same rule here, we actually end up with the worst path

Let’s try on this example:

Maybe we should not just consider the smallest option from a single node?
Maybe we should consider the paths from past nodes too?

Unsurprisingly, it looks like it might be really important to know how far we’ve travelled so far

Principle of Optimality¶

Fastest way to get to Halifax’s airport
Fastest way to Truro?
Fastest way to New Glasgow?

Given that we definitely have the shortest path to the airport:

Is there not a shorter path to Truro from New Glasgow?
- If there was one, it would have been apart of the shortest path to the airport

Our shortest path to the Halifax airport consists of:

The optimal path from Antigonish to New Glasgow
The optimal path from new Glasgow to Truro
The optimal path from Truro to the airport

This is called the Principle of Optimality!!

Dijkstra’s Algorithm¶

Shortest path algorithm

Intuition

Do a breadth first search
- Start spanning out
We know that the optimal path will be a collection of optimal paths
- Always remember the optimal path to nodes along the way
- And remember the total distance so far
- If we find a more optimal path to a vertex/node, we update it.
We prioritize paths we know are shorter/faster
- Always look at what took the least amount of time to get to
  
  What has the least weight from the start/source
- Think of highways vs dirt mountain roads

Let’s take these ideas and see if we can work out the algorithm

Activity

Use the above ideas, and find the shortest path from A to J.

Algorithm:

Set all vertices/nodes as unvisited
Set all vertices/nodes’ distance from source to infinity
Set all vertices/nodes’ previous node to None/Null
Set start/source to current, and set it’s distance to 0
For the current node:
- Note: whenever a node is the current, we know its distance from the start is optimal
- If current is the target
  - We’re done!
- For each unvisited neighbour:
  - Calculate the distance to the neighbour through current (current’s dist + edge dist)
  - If this distance is less than the neighbour’s current distance from source:
    
    Update it
    
    Set previous node to current (remember where we came from)
- Set current to visited
- Set unvisited node with smallest distance/weight to current
  - If there are none left, or everything left has a dist of infinity
    
    Then there must not be a solution

Priority Queue¶

We’re pulling things from the unvisited list in order of smallest distance so far
We can think of this distance as a priority

What is it?

Enqueue things into a priority queue with a priority
When we dequeue things, we get the thing with the lowest priority

Implementation

Could use a list. Either:
- On insert, do a linear search and find where something goes.
  
  $O(n)$ enqueue, $O(1)$ dequeue
- OR, on remove, do a linear search for the smallest thing.
  
  $O(1)$ enqueue, $O(n)$ dequeue

Heaps¶

Assuming 0 based indexing of array/list:

$left = i*2 + 1$

$right = i*2 + 2$

$parent = \lfloor\frac{i-1}{2}\rfloor$

Min Heap as Priority Queue

Insert/Enqueue

Max distance something could bubble?

$O(log_2(n))$

Remove/Dequeue

Max distance something could bubble?

$O(log_2(n))$

Update

Assuming an adjacency list
- Faster access to neighbours
With an auxilliary data structure, we can easily access information in the heap
- A dictionary keeping track of the indices of each vertex in the heap
We can just remove the item, and re-enqueue it.
- $O(log_2(n))$