******************** Dijsktra's Algorithm ******************** Previously ========== * We introduced graphs. * We covered a single source shortest-path algorithm for unweighted graph :math:`G = (V, E)`. * Single source means that we calculate the shortest path from a specific node :math:`s \in V` to any other nodes :math:`v_k \in V`. * Unweighted graphs are graphs that doesn't have a weight (or cost) on the edges. * The algorithm we covered is Breadth-First-Search (BFS). * The idea: .. code-block:: function BFS(Graph, source): Create a queue Q. Q.insert(s). while Q not empty: u = Q.pop() visit(u) for all v adjacent to u: if v not marked or visited: Mark v Q.insert(v) We took the following graph as example: .. figure:: ../figs/recap/unweighted_graph.drawio.png :align: center After applying the algorithm, we obtained: .. figure:: ../figs/recap/bfs.drawio.png .. admonition:: Activity :class: activity What happens if the graph has weighted edges? .. figure:: ../figs/recap/weighted_graph.drawio.png :align: center Dijsktra's Algorithm ==================== * Dijsktra's algorithm is a single source shortest-path algorithm for **weighted** graph. * It is also a greedy algorithm, meaning that we always take the closest node not already visited. * To work we need a few assumptions: * There is a path between the source (or start) and every other node in the graph. * All edges have a positive weight. Application ----------- - Computer networking - Transportation - Geographic information systems How is it working? ------------------ To explain how the algorithm works, we will consider the following graph: .. figure:: ../figs/dijkstra/weighted_graph.drawio.png :align: center * We consider two sets of nodes :math:`S` and :math:`V-S`. * :math:`S`: set of nodes with the shortest distance already computed. * :math:`V-S`: set of nodes remaining. * We also need two arrays :math:`d` and :math:`p`: * :math:`d[v]`: the shortest distance from :math:`s` to :math:`v`. * :math:`p[v]`: the predecessor of :math:`v` in the path from :math:`s` to :math:`v`. * We initialize :math:`S` with :math:`0`. * We place every nodes remaining in :math:`V-S`. * For each adjacent :math:`v` of :math:`s`, we set :math:`d[v]` equal to :math:`w(s, v)`. * The predecessor is :math:`0` for every :math:`v`. .. figure:: ../figs/dijkstra/example-01.drawio.png :align: center * Now we find the vertex (node) :math:`u \in V-S` that has the smallest :math:`d[v]`. * For every node :math:`v` adjacent to :math:`u`: * if :math:`d[u] + w(u,v) < d[v]`, we update :math:`d[v]`. * and we set :math:`p[v]` to :math:`u`. * In our example: .. figure:: ../figs/dijkstra/example-02.drawio.png :align: center * We continue: .. figure:: ../figs/dijkstra/example-03.drawio.png :align: center * Again: .. figure:: ../figs/dijkstra/example-04.drawio.png :align: center * Finally: .. figure:: ../figs/dijkstra/example-05.drawio.png :align: center Algorithm --------- * Now we can discuss how to implement it. * A straightforward implementation is to use a list to maintain :math:`V-S`: .. code-block:: function Dijkstra(Graph, source): create empty list L for all vertex v in G: d[v] = infinity p[v] = null L.insert(v) d[source] = 0 while L is not empty: u = vertex in L with smallest d value L.remove(u) for each neighbor v of u: alt = dist[u] + w(u, v) if alt < dist[v]: d[v] = alt p[v] = u .. admonition:: Activity :class: activity What is the time complexity of this implementation? The time complexity if :math:`O(|V|^2)`: * The initialization takes :math:`O(|V|)` as we need to insert every nodes in the list. * The while loop is :math:`O(|V|)` as we need to loop over every nodes. * We have two nested loops inside. * The first is finding the closest node, so a linear search :math:`O(|V|)`. * The second one is checking each adjacent not in :math:`S`, so :math:`O(|V|)`. | * We can improve this by using a binary heap. .. code-block:: function Dijkstra(Graph, source): create empty priority queue Q dist[source] = 0 for each vertex v in Graph: if v != source: dist[v] = infinity p[v] = null Q.insert(v, dist[v]) Q.insert(source, 0) while Q is not empty: u = Q.extract_min() for each neighbor v of u: alt = dist[u] + w(u, v) if alt < dist[v]: dist[v] = alt p[v] = u Q.decrease_key(v, alt) return dist * The initialization is :math:`O(|V|\log |V|)`. * :code:`Q.extract_min()` is :math:`O(\log |V|)`. * :code:`Q.decrease_key(v, alt)` is :math:`O(\log |V|)`. * So the loop checking the adjacent nodes is :math:`O(|E|\log |V|)`. .. important:: We visit each edges at most once! Thus the complexity is the complexity of updating all the adjacent nodes :math:`O(|E|\log |V|)`. Proof of Correctness -------------------- * Let :math:`G = (V, E)` be a weighted, directed graph, where :math:`V` is the set of vertices and :math:`E` is the set of edges, and let :math:`s` be the source vertex. * Let :math:`d[v]` be the current distance estimate from the source vertex :math:`s` to vertex :math:`v`. * We claim: .. admonition:: Claim :class: important Each time Dijkstra's algorithm selects a path to a node :math:`v`, that path is shorter than every other path to :math:`v`. Base case ********* * We start with the base case, :math:`|S| = 1`. * :math:`d[s] = 0` and :math:`d[v] = +\infty, \forall v \neq s`. * The claim hold for :math:`S = {s}`. .. figure:: ../figs/dijkstra/proof_01.drawio.png :align: center :width: 20% | Hold for :math:`n` ****************** * Suppose the claim hold when :math:`|S| = n, n \geq 1`. .. figure:: ../figs/dijkstra/proof_02.drawio.png :align: center :width: 50% | Induction step ************** * Dijkstra's algorithm add one more node :math:`v` to :math:`S`. * So :math:`|S| = n+1`. * let :math:`(u,v)` the final edge on the path :math:`s-v` denoted :math:`P_v`. * By induction hypothesis :math:`P_u` is the shortest path from :math:`s` to :math:`u`. .. figure:: ../figs/dijkstra/proof_03.drawio.png :align: center :width: 70% | * Now, consider any other path :math:`s-v`, denoted :math:`P'_v`. * We want to show that :math:`P'_v` is as least as long as :math:`P_v`. * :math:`P'_v` must leave :math:`S` somewhere. .. figure:: ../figs/dijkstra/proof_03.drawio.png :align: center :width: 70% | * Let denote :math:`y` the node on :math:`P'_v`, but not in :math:`S`. * Let denote :math:`x` the node before :math:`y`, but in :math:`S`. .. figure:: ../figs/dijkstra/proof_03.drawio.png :align: center :width: 70% | * :math:`P'_v` cannot be shorter than :math:`P_v`. * At iteration :math:`n+1`, Dijkstra considered :math:`y` and rejected it. * It chose :math:`v` instead. * So there is not path :math:`s-y` through :math:`x` shorter than :math:`P_v`. Negative Weights ---------------- * Until now, we assume that the graph only has positive weights. * If there are negative weights, then Dijkstra is not optimal. .. admonition:: Example :class: example * Consider the following example: .. figure:: ../figs/dijkstra/negative_00.drawio.png :align: center :width: 30% | * We initialize :math:`S` and :math:`V-S`. * We update :math:`d[v]` for every adjacent node of :math:`s`. .. figure:: ../figs/dijkstra/negative_01.drawio.png :align: center :width: 80% | * We choose :math:`1` and add it to :math:`S`. * :math:`1` has no adjacent nodes in :math:`V-S`. .. figure:: ../figs/dijkstra/negative_02.drawio.png :align: center :width: 80% | * We add :math:`2` to :math:`S`. * :math:`2` has no adjacent nodes in :math:`V-S`. * So, we don't update :math:`1`! .. figure:: ../figs/dijkstra/negative_03.drawio.png :align: center :width: 80% | .. important:: * This is why Dijkstra’s algorithm doesn’t work with negative weight. * Once a node is added to :math:`S`, we consider that we have the shortest distance to it.