Lecture 17 - Notes

March 10, 2016

Shortest Path Algorithms

definition: Given a directed edge-weighted graph, find the shortest path from $s$ to $w$.

We begin by setting the distance to $s$ to $0$ and the distance to $w$ to $\infty$ for all other vertices $v$. We relax an when we evaluate the actual shortest path from that node to $w$.

Dijkstra's Algorithm

definition: To find the shortest path between $a$ and $b$. Pick the unvisited vertex with the lowest distance and calculate the distance through it to each unvisited neighbour, then update the neighbour's distance if smaller. Mark the vertex visited (or red) when done with neighbours.

Directed Acyclic Graph

On a directed acyclic graph the algorithm takes $O(E+V)$.