Goodrich Chapter 12

Dijkstra's algorithm is a weighted breadth-first search. it uses a greedy heuristic to select the next edge. It works by starting with an empty "cloud" of vertices, and adds vertices to the cloud in order of their distance from s.

The end result of Dijkstra's algorithm is the length of the shortest distance (weighted path) from the source vertex s to all other vertices v on the graph G.

Edge Relaxation

The central idea in Dijkstra's algorithm is edge relaxation. To implement edge relaxation, we define a starting vertex s, and a map distance, which maps vertices to distances.

Specifically distance[v] stores the minimum distance so far from the source vertex s to some other vertex v. Initially, this quantity is infinity (i.e., initially we do not have any path connecting s to v, because we have not explored the graph), except for vertex s - distance[s] is initially 0.

We then define a set of vertices, which we will call the cloud, that consists of vertices that have been visited. This is initially the empty set.

Next, we add a new vertex u (not currently in the cloud) to the cloud. We select the next vertex u based on the node with the smallest value of distance[u] (using a Priority Queue).

Next, we loop over each vertex v adjacent to u, and update distance[v]. Note that this is updating the distance from s to the neighbors of u, not the distance from s to u. This is looking ahead to the next step, when we will look for the next vertex with the smallest distance from s. This step is where the actual relaxation procedure occurs - it takes an old estimate and checks if it can be improved to get closer to the true value.

We then move on to the next step: select the next vertex u (not in the cloud) based on the node with the smallest value of distance[u].

Pseudocode

Edge Relaxation Pseudocode

Pseudocode for edge relaxation is a search for shorter distances. It compares the current shortest distance to the shortest distance based on the "hop" from a current vertex (via a traversal) to the vertex in question:

// This procedure occurs during a weighted breadth-first search starting at a source vertex s
// It updates the shortest distances from the source vertex s to the vertex in question v
if distance[u] + w(u,v) < distance[v]:
    distance[v] = distance[u] + w(u,v)

By performing this edge relaxation procedure during a weighted breadth-first search, we can assemble a map/dictionary "distance" that contains the shortest path from a source node s to a given node v.

Dijkstras Agorithm Psuedocode

// Assembles a map "distance" containing the shortest path 
// from a source vertex s to every other vertex
// in a graph g
def shortest_path(g,s):
    initialize distance map
    distance[:] = infinity
    distance[s] = 0
    initialize a priority queue pq containing all vertices of g

    while pq is not empty:

        // pull new vertex u into cloud
        // the first time thru, everything is infinity except s
        // so we are considering s
        u = pq.remove_min()

        // update values of distance[neighbors of s]
        for each vertex v adjacent to u:
            if v in pq:
                // edge relaxation - 
                // this ensures we update info at each step,
                // and that we are always making the best possible choice
                if distance[u] + w(u,v) < distance[v]:
                    distance[v] = distance[u] + w(u,v)
                    update pq[v] with new value of distance[v]
    return distance

Properties

If a vertex is pulled into the cloud, the edge relaxation procedure guarantees it is the shortest path from the source vertex s to the vertex v.

Big O Cost

The big O cost of Dijkstra's algorithm depends on the data structure implemented. It also depends on the data structure used to implement the priority queue.

Dijkstra's algorithm is an example of a cascade of complexity - it utilizes several data structures, and its big O runtime cost depends on the data structures used.

The priority queue relies on the ability to update items that are in the priority queue. This can be done by utilizing an adaptable priority queue, which returns a reference to any items added to the priority queue so that they can be updated later. If these items are stored in a map, we can accomplish an O(1) lookup to retrieve items already in the priority queue, and update them in O(1). This may lead to other costs (specifically, the costs associated with re-ordering the priority queue).

If we use an adjacency list or adjacency map, we can iterate through the n vertices in $O(n)$ time. Thus, the nested for loop will take

$\sum _{v\in G}{\mbox{outdegree}}(u)$

(Sum of all out-edges, for each vertex adjacent to u)

which is $O(m)$

The outer while loop will run in $O(n)$ time, since a new vertex is added to the cloud each iteration, and there are n vertices.

The priority queue requires inserting n items (inserting each vertex once), and the maximum size of hte queue is n.

Each of the n iterations requires a call to remove the minimum item, in a queue of size n. For each neighbor v of u, we perform edge relaxation and may need to update the key of v. In the worst case, we will have to perform an update for each edge of each vertex in the graph. To summarize the operations required:

n insertions into priority queue pq
n calls to remove min method of pq
m calls to update method of pq

Each of the above operations can be run in $O(\log n)$ if we implement the priority queue as a heap, giving an overall big O cost of $O((n+m)\log n)$ , or, writing only in terms of n, $O(n^{2}\log n)$ .

If we use an unsorted priority queue, we require more time to extract the minimum but less time to update items - removing minimum costs $O(n)$ but updating requires $O(1)$ . Thus, the implementation is $O(n^{2}+m)$ , or just in terms of n, $O(n^{2})$ .

Implementation Choices

From the above we can see we have two choices for implementing the priority queue:

heap-based priority queue
unsorted priority queue

The heap implementation requires $O((n+m)\log n)$

The unsorted sequence implementation requires $O(n^{2})$

Both implementations are about equal in complexity of the algorithm, and both are about equal in constant factors for worst-case running time.

Therefore, for a small number of edges, $m<{\dfrac {n^{2}}{\log n}}$ we go with the heap-based implementation. For a larger number of edges $m>{\dfrac {n^{2}}{\log n}}$ , we go with an unsorted sequence implementation.

Dijkstra's algorithm can therefore compute the distance from s to all other vertices on the graph G in the better of $O(n^{2})$ and $O((n+m)\log n)$ time.

If we want to achieve further improvements, we can use a Fibonacci heap, which is a more advanced data structure allowing for a big O cost of $O(m+n\log n)$ runtime.

Reconstructing Shortest Path Tree

The above pseudocode yields a distance map - each entry/key is a vertex that maps to a value that is the shortest distance from the source node to the given vertex. This is useful, but not as useful as a tree structure that would not just give the distance but actually give THE PATH.

We can construct the shortest path tree from the distance map using the edge relaxation relation: namely, that if u is the vertex that precedes the last vertex v on the shortest path, the following must be true:

distance[u] + w(u,v) = distance[v]

Flags

Graphs/Dijkstra

From charlesreid1

Contents