DijkstrasAlgorithm.ptx

<?xml version="1.0" ?><section xml:id="graphs_dijkstras-algorithm">
        <title>Dijkstra's Algorithm</title>

        <p><idx>dijkstra's algorithm</idx>
            The algorithm we are going to use to determine the shortest path is
            called <q>Dijkstra's algorithm.</q> Dijkstra's algorithm is an iterative
            algorithm that provides us with the shortest path from one particular
            starting node to all other nodes in the graph. Again this is similar to
            the results of a breadth first search.</p>
        <p>To keep track of the total cost from the start node to each destination
            we will make use of the <c>dist</c> variable in the Vertex class.
            The <c>dist</c> variable will contain the current total weight of
            the smallest weight path from the start to the vertex in question. The
            algorithm iterates once for every vertex in the graph; however, the
            order that we iterate over the vertices is controlled by a priority
            queue. The value that is used to determine the order of the objects in
            the priority queue is <c>dist</c>. When a vertex is first created <c>dist</c>
            is set to a very large number. Theoretically you would set <c>dist</c> to
            infinity, but in practice we just set it to a number that is larger than
            any real distance we would have in the problem we are trying to solve.</p>
        <p>The code for Dijkstra's algorithm is shown in <xref ref="graphs_lst-shortpath"/>. When the algorithm finishes the distances are set
            correctly as are the predecessor links for each vertex in the graph.</p>
        
        <listing xml:id="graphs_lst-shortpath">
            <title>Dijkstra's Algorithm</title>
            <program language="python" label="graphs_lst-shortpath-prog"><code>
from pythonds.graphs import PriorityQueue, Graph, Vertex

def dijkstra(aGraph,start):
    pq = PriorityQueue()
    start.setDistance(0)
    pq.buildHeap([(v.getDistance(),v) for v in aGraph])
    while not pq.isEmpty():
        currentVert = pq.delMin()
        for nextVert in currentVert.getConnections():
            newDist = currentVert.getDistance() \
                    + currentVert.getWeight(nextVert)
            if newDist &lt; nextVert.getDistance():
                nextVert.setDistance( newDist )
                nextVert.setPred(currentVert)
                pq.decreaseKey(nextVert,newDist)
            </code></program>
        </listing>

        <listing xml:id="graphs_lst-shortpath2">
            <title>Dijkstra's Algorithm C++</title>
            <program language="c++" label="graphs_lst-shortpath-prog2"><code><![CDATA[
#include "Graph.h"
#include <iostream>
using namespace std;

vector<Node> dijkstra(const vector<vector<Node>>&amp; graph, int start) {
    vector<Node> distances;
    for (int i = 0; i &lt; graph.size(); i++) {
        distances.push_back(Node(INF, -1));
    }
    distances[start] = Node(0, start);

    BinHeapMap pq;
    pq.insert(0, start);

    while (!pq.isEmpty()) {
        Node current = pq.delMin();
        int distance = current.getKey();
        int vertex = current.getValue();

        if (distance &gt; distances[vertex].getKey()) {
            continue;
        }

        for (int i = 0; i &lt; graph[vertex].size(); i++) {
            Node neighbor = graph[vertex][i];

            int newDistance = distance + neighbor.getKey();

            if (newDistance &lt; distances[neighbor.getValue()].getKey()) {
                distances[neighbor.getValue()] = Node(newDistance, vertex);
                pq.insert(newDistance, neighbor.getValue());
            }
        }
        cout &lt;&lt; "" &lt;&lt; endl;
    }
   return distances;
}
            ]]></code></program>
        </listing>
        <p>Dijkstra's algorithm uses a priority queue. You may recall that a
            priority queue is based on the heap that we implemented in the Tree Chapter.
            There are a couple of differences between that
            simple implementation and the implementation we
            use for Dijkstra's algorithm. First, the <c>PriorityQueue</c> class stores
            tuples of key, value pairs. This is important for Dijkstra's algorithm
            as the key in the priority queue must match the key of the vertex in the
            graph. Secondly the value is used for deciding the priority, and thus
            the position of the key in the priority queue. In this implementation we
            use the distance to the vertex as the priority because as we will see
            when we are exploring the next vertex, we always want to explore the
            vertex that has the smallest distance. The second difference is the
            addition of the <c>decreaseKey</c> method. As you can see, this method is used when the distance to a vertex that
            is already in the queue is reduced, and thus moves that vertex toward
            the front of the queue.</p>
        <p>Let's walk through an application of Dijkstra's algorithm one vertex at
            a time using the following sequence of figures as our guide. We begin with the vertex
            <m>u</m>. The three vertices adjacent to <m>u</m> are
            <m>v,w,</m> and <m>x</m>. Since the initial distances to
            <m>v,w,</m> and <m>x</m> are all initialized to <c>sys.maxint</c>,
            the new costs to get to them through the start node are all their direct
            costs. So we update the costs to each of these three nodes. We also set
            the predecessor for each node to <m>u</m> and we add each node to the
            priority queue. We use the distance as the key for the priority queue.
            The state of the algorithm is shown in <xref ref="fig-dija"/>.</p>
        <p>In the next iteration of the <c>while</c> loop we examine the vertices that
            are adjacent to <m>x</m>. The vertex <m>x</m> is next because it
            has the lowest overall cost and therefore bubbled its way to the
            beginning of the priority queue. At <m>x</m> we look at its neighbors
            <m>u,v,w</m> and <m>y</m>. For each neighboring vertex we check to
            see if the distance to that vertex through <m>x</m> is smaller than
            the previously known distance. Obviously this is the case for
            <m>y</m> since its distance was <c>sys.maxint</c>. It is not the case
            for <m>u</m> or <m>v</m> since their distances are 0 and 2
            respectively. However, we now learn that the distance to <m>w</m> is
            smaller if we go through <m>x</m> than from <m>u</m> directly to
            <m>w</m>. Since that is the case we update <m>w</m> with a new
            distance and change the predecessor for <m>w</m> from <m>u</m> to
            <m>x</m>. See <xref ref="fig-dijb"/> for the state of all the vertices.</p>
        <p>The next step is to look at the vertices neighboring <m>v</m> (see <xref ref="fig-dijc"/>). This
            step results in no changes to the graph, so we move on to node
            <m>y</m>. At node <m>y</m> (see <xref ref="fig-dijd"/>) we discover that it is cheaper to get
            to both <m>w</m> and <m>z</m>, so we adjust the distances and
            predecessor links accordingly. Finally we check nodes <m>w</m> and
            <m>z</m> (see see <xref ref="fig-dije"/> and see <xref ref="fig-dijf"/>). However, no additional changes are found and so the
            priority queue is empty and Dijkstra's algorithm exits.</p>
        
        <figure xml:id="fig-dija">
            <caption>Tracing Dijkstra's Algorithm.</caption>
                <image source="Graphs/dijkstraa.png" width="80%">
                <description><p>The image illustrates the initial state of Dijkstra's Algorithm being traced on a weighted graph. The graph includes six nodes: u, v, w, x, y, and z. Node u is marked as the starting point with a tentative distance of zero (d=0), while other nodes are yet to be visited and have undefined distances. Edges connecting the nodes have varying weights, such as the edge from u to x has a weight of 2, and the edge from x to v has a weight of 1. A priority queue (PQ) is depicted at the bottom, currently holding nodes x, v, and w, which will be processed according to the algorithm.</p></description>
                </image>
            </figure>
        
        <figure xml:id="fig-dijb">
            <caption>Tracing Dijkstra's Algorithm.</caption>
                <image source="Graphs/dijkstrab.png" width="80%">
                <description><p>This image further traces Dijkstra's Algorithm on the same weighted graph. The priority queue (PQ) at the bottom has been updated to contain only nodes v and w. Node x has been visited with the shortest distance from u determined (d=1), indicated by a solid line. Other nodes have tentative distances, like node v with a distance of 2 (d=2). Dashed lines indicate unconfirmed paths that are still under consideration.</p></description>
                </image>
            </figure>

        <figure xml:id="fig-dijc">
            <caption>Tracing Dijkstra's Algorithm.</caption>
                <image source="Graphs/dijkstrac.png" width="80%">
                <description><p>The image continues the progression of Dijkstra's Algorithm on the graph. Node v has now been confirmed with the shortest path from u (d=2) and is connected by solid lines. The priority queue (PQ) at the bottom now includes only node w. Node x shows the confirmed shortest path from u, and node y has a tentative distance of 2 (d=2). The algorithm visually demonstrates the process of finding the shortest paths from a single source to all other nodes in the graph.</p></description>
                </image>
            </figure>
        
        <figure xml:id="fig-dijd">
            <caption>Tracing Dijkstra's Algorithm.</caption>
                <image source="Graphs/dijkstrad.png" width="80%">
                <description><p>The image shows a continuation of Dijkstra's Algorithm on a weighted graph. The graph's nodes u, v, w, x, y, and z are connected by directed edges with weights. Node w is the current focus, indicated by the priority queue (PQ) containing only w. Nodes u, x, and v have confirmed shortest paths with solid lines leading to them, and their distances from the starting node u are marked as d=0, d=1, and d=2, respectively. Dashed lines suggest potential paths still under consideration.</p></description>
                </image>
            </figure>
        

        <figure xml:id="fig-dije">
            <caption>Tracing Dijkstra's Algorithm.</caption>
                <image source="Graphs/dijkstrae.png" width="80%">
                <description><p>This step in Dijkstra's Algorithm shows node w with a confirmed shortest path from the starting node (d=3). The priority queue (PQ) at the bottom now contains only node z. The graph is further resolved with nodes u, x, v, and y having confirmed shortest paths, displayed with solid lines and distances marked. The algorithm's process is nearing completion, with almost all nodes having the shortest paths determined.</p></description>
                </image>
            </figure>
        

        <figure xml:id="fig-dijf">
            <caption>Tracing Dijkstra's Algorithm.</caption>
                <image source="Graphs/dijkstraf.png" width="80%">
                <description><p>The final image depicts the weighted graph after the completion of Dijkstra's Algorithm. All nodes have confirmed shortest paths from the starting node u, which are shown with solid lines. The priority queue (PQ) is now empty, indicating that the algorithm has finished running. Each node has a definitive shortest distance from u (d=0, d=1, d=2, d=3, etc.), and the pathfinding process is complete, showcasing the algorithm's effectiveness in solving the shortest path problem.</p></description>
                </image>
            </figure>
        <p>It is important to note that Dijkstra's algorithm works only when the
            weights are all positive. You should convince yourself that if you
            introduced a negative weight on one of the edges to the graph that the algorithm would never exit.</p>
        <p>We will note that to route messages through the Internet, other
            algorithms are used for finding the shortest path. One of the problems
            with using Dijkstra's algorithm on the Internet is that you must have a
            complete representation of the graph in order for the algorithm to run.
            The implication of this is that every router has a complete map of all
            the routers in the Internet. In practice this is not the case and other
            variations of the algorithm allow each router to discover the graph as
            they go. One such algorithm that you may want to read about is called
            the <q>distance vector</q> routing algorithm.</p>
        <reading-questions xml:id="rq-dijkstras-algo">
            <title>Reading Question</title>
            
            
            
        
    <exercise label="dijkstraq1">
        <statement>

            <p>What purpose does the Priority Queue in the Dijkstra's algorithm serve?</p>

        </statement>
<choices>

            <choice>
                <statement>
                    <p>It only holds a series of vertices to traverse.</p>
                </statement>
                <feedback>
                    <p>Not quite, Priority Queues serve a purpose beyond storage.</p>
                </feedback>
            </choice>

            <choice>
                <statement>
                    <p>It holds an unsorted list of unvisited vertices.</p>
                </statement>
                <feedback>
                    <p>No, the vertices will be sorted.</p>
                </feedback>
            </choice>

            <choice>
                <statement>
                    <p>It notes what vertices have been visited.</p>
                </statement>
                <feedback>
                    <p>No, it does not store any visited vertices.</p>
                </feedback>
            </choice>

            <choice correct="yes">
                <statement>
                    <p>It holds an appropriately sorted list of vertices to traverse.</p>
                </statement>
                <feedback>
                    <p>Correct!</p>
                </feedback>
            </choice>
</choices>

    </exercise>
</reading-questions>  
  </section>