**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**: :math:`G = (V, E)`. **Vertices**: :math:`V = \{v_1, v_2, ... , v_n\}`. **Edges**: :math:`E = \{e_1, e_2, ... e_m\}`, where :math:`e_i \in \{(a, b) | a, b \in V\}` **Example** .. image:: ../img/graph.png :height: 200px :align: left | | :math:`V = \{A, B, C, D\}` :math:`E = \{(A, B), (B, C), (A, C), (C, D)\}` | | | | **Implementation** .. image:: ../img/listmat.png :height: 150px **Weighted Graphs** .. image:: ../img/wgraph.png :height: 200px * Each edge has a weight associated with it * More general **Airports** .. image:: ../img/airports.png :height: 300px **Road Networks** (kinda' to scale) .. image:: ../img/NS.png :height: 300px Problem: Route Planning ^^^^^^^^^^^^^^^^^^^^^^^ .. image:: ../img/path.png :height: 300px * 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)** .. admonition:: Activity Find all paths from A to J. 1. A -> B -> D -> G -> J (length: 10) 2. A -> B -> D -> H -> J (length: 9) 3. A -> B -> D -> F -> H -> J (length: 7) 4. A -> C -> E -> F -> H -> J (length: 6) 5. A -> C -> E -> F -> H -> D -> G -> J (length: 17) 6. A -> C -> E -> F -> D -> G -> J (length: 11) 7. 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 .. image:: ../img/largeG.jpg :height: 300px **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? .. image:: ../img/greedy.png :height: 300px 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: .. image:: ../img/greedyBad.png :height: 200px * If we follow the same rule here, we actually end up with the **worst** path Let's try on this example: .. image:: ../img/greedyBad2.png :height: 200px * Maybe we should not just consider the smallest option from a single node? * Maybe we should consider the paths from past nodes too? .. image:: ../img/greedyBad3.png :height: 200px * Unsurprisingly, it looks like it might be **really** important to know how far we've travelled so far Principle of Optimality ^^^^^^^^^^^^^^^^^^^^^^^ .. image:: ../img/NS2.png :height: 300px * 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** .. image:: ../img/path.png :height: 300px .. admonition:: Activity Use the above ideas, and find the shortest path from A to J. **Algorithm**: 1. Set all vertices/nodes as *unvisited* 2. Set all vertices/nodes' distance from source to infinity 3. Set all vertices/nodes' previous node to None/Null 4. Set start/source to *current*, and set it's distance to 0 5. 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. * :math:`O(n)` enqueue, :math:`O(1)` dequeue * OR, on remove, do a linear search for the smallest thing. * :math:`O(1)` enqueue, :math:`O(n)` dequeue Heaps ^^^^^ .. image:: ../img/heap.png :height: 300px Assuming 0 based indexing of array/list: :math:`left = i*2 + 1` :math:`right = i*2 + 2` :math:`parent = \lfloor\frac{i-1}{2}\rfloor` **Min Heap as Priority Queue** **Insert/Enqueue** .. image:: ../img/bup.png :height: 300px Max distance something could bubble? * :math:`O(log_2(n))` **Remove/Dequeue** .. image:: ../img/bdown.png :height: 300px Max distance something could bubble? * :math:`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. * :math:`O(log_2(n))` Complexity ^^^^^^^^^^ **Lazy** * :math:`|E| = O(|V|^2)` Therefore: :math:`O(|V|^2)` **Less Lazy** How many things could we possibly add to our heap? * All the vertices * :math:`O(|V|)` How much work is it to add each thing to the heap? * :math:`O(log_2|V|)` * (:math:`O(|V|)` with a linked list) How many times might we need to update something in the heap * Each edge might cause an update * :math:`O(|E|)` How much work is it to update something in the heap? * :math:`O(log_2|V|)` * (:math:`O(|V|)` with a linked list) Therefore: :math:`O(|V|log_2|V| + |E|log_2|V|)` or :math:`O((|V| + |E|)log_2|V|)` **Linked List** :math:`O(|V|^2 + |E|*|V|)` or :math:`O(|V|^2)` A* (A-Star) ^^^^^^^^^^^ **Can be dumb though** .. image:: ../img/bad.png :height: 300px .. admonition:: Activity How would Dijkstra's algorithm traverse this graph? When you want to get somewhere, what do *you* do to plan your route? .. image:: ../img/map2.png :height: 300px