# 10^{th} Friday Fun Session – 17^{th} Mar 2017

Dijkstra’s algorithm is a Single-Source Shortest Path (SSSP) algorithm developed by Edsger Wybe Dijkstra. It uses a greedy process and yet finds the optimal solution. It looks similar to Breadth-first search.

### Compare to Bellman-Ford

It is asymptotically the fastest SSSP algorithm, at a cost *O(|E|+|V|log|V|), *when min-priority queue implemented by Fibonacci heap is used.

That is quite cheap, given Bellman-Ford’s complexity of *O(|V||E|)* to find the same, something that can become prohibitively expensive for a dense graph having *|V| ^{2 }*edges.

However, while Bellman-Ford can work with negative edge and can detect negative cycle, Dijkstra’s algorithm cannot work with negative edge. Since it cannot work with negative edge, there is no question of detecting negative cycle at all.

### Standard Algorithm

dist[] //shortest path vector p[] //predecessor vector, used to reconstruct the path Q //vertex set for each vertexvin Graph dist[v] = ∞ p[v] = undefined addvto Q dist[s] = 0 while Q is not emptyu= vertex with min dist[] value removeufrom Q for each neighborvofualt = dist[u] + weight(u,v) if alt < dist[v] dist[v] = alt p[v] =ureturn dist[], p[]

Given source vertex *s*, it finds the shortest distance from *s* to all other vertices. At first, it initializes *dist[]* vector to infinite to mean that it cannot reach any other vertex. And sets *dist[s] = 0* to mean that it can reach itself at a cost of 0, the cheapest. All vertices including itself are added to the vertex set *Q*.

Then, it chooses the vertex with min *dist[]* value. At first, *s* (set to *u*) would be chosen. Then using each of the outgoing edges of *u* to *v*, it tries to minimize *dist[v]* by checking whether *v* can be reached via *u* using edge (*u*, *v*). If yes, *dist[v]* is updated. Then again it retrieves vertex *u* with the cheapest dist[*u*] value and repeats the same. This continues till *Q* is not empty. Whenever, a vertex *u* is removed from *Q*, it means that the shortest distance from *s* to *u* is found.

Since we are retrieving *|V|* vertices from *Q*, and for each vertex, trying with all its edges (=*|V|*, at max), to minimize distance to other vertices, the cost can be *|V| ^{2}*.

So, here we see a greedy process where it is retrieving the vertex with min *dist[]* value.

Since retrieving a vertex *u* from *Q *means that we found the minimum distance from *s* to *u,* if we are solving shortest path from a single source *s* to a single destination *d*, then when *u* matches the destination *d*, we are done and can exit.

It can also be noted that from source *s*, we find the shortest distances to all other vertices, in the ascending order of their distances.

Finally, we see that *dist[]* vector is continuously changing. And each time when we retrieve a vertex *u*, we choose the one with min *dist[]* value. That indicates using min-priority queue might be the right choice of data structure for this algorithm.

### Using Fibonacci Heap

dist[] //shortest path vector p[] //predecessor vector, used to reconstruct the path Q //priority queue, implemented by Fibonacci Heap dist[s] = 0 for each vertex v if(s!=v) dist[v] = ∞ p[v] = undefined Q.insert_with_priority(v, dist[v]) // insert while Q.is_empty() = false u = Q.pull_with_min_priority() // find min and delete min for each neighborvofualt = dist[u] + weight(u,v) if alt < dist[v] dist[v] = alt p[v] =uQ.decrease_priority(v, alt) //decrease key return dist[], p[]

In the above algorithm, we have used a function called *decrease_priority()*, something that is absent in standard priority queue but present in Fibonacci heap. So the above algorithm is implemented using Fibonacci heap.

Fibonacci heap is a special implementation of a priority queue that supports *decrease key* *(decrease_priority())* operation. Meaning, we can decrease the value of a key while it is still inside the priority queue. And this can be achieved by using constant amortized time for *insert*, *find min* and *decrease key* operation and *log (n)* time for *delete min* operation.

As for cost, since we have called *delete* operation for each of the *v* vertices, and we have treated each of the *|E|* edges once, the cost here is *O(|E|+|V|log|V|), as* mentioned at the beginning of this post, as the cost of Dijkstra’s algorithm.

### Using Standard Priority Queue

Standard priority queue implementation takes *log (n) *time for both *insert* and *delete* operation and constant time for *find min* operation. But there is no way to change the key value (*decrease key*) while the item is still in the priority queue, something Dijkstra’s algorithm might need to do quite frequently as we have already seen.

If standard priority queue is used, one has to *delete* the item from the priority queue and then *insert* into it again, costing *log (n)* each time, or an alternative to that effect. However, as long as standard priority queue is used, it is going to be slower than Fibonacci heap. With standard priority queue, the algorithm would look like below:

dist[] //shortest path vector p[] //predecessor vector, used to reconstruct the path Q //standard priority queue for each vertexvdist[v] = ∞ p[v] = undefined dist[u] = 0 Q.insert_with_priority(u, dist[u]) // insert while Q.is_empty() = false u = Q.pull_with_min_priority() // find min and delete min for each neighborvofualt = dist[u] + weight(u,v) if alt < dist[v] dist[v] = alt p[v] =uinsert_with_priority(v, alt) //insertveven if already exists return dist[], p[]

There are two differences from the earlier algorithm:

First, we have not inserted all vertices into the standard priority queue at first, rather inserted the source only.

Second, instead of decreasing priority that we cannot do using standard priority queue, we have kept on inserting vertex *v* when *dist[v]* decreases. That might mean, inserting a vertex *v* again while it is already there inside the queue with a higher priority/dist[*v*]. That is another way of pushing aside the old entry (same *v* but with higher priority) out of consideration for the algorithm. When shortest distances from source *s* to all other vertices *v* are found, those pushed aside vertices will be pulled one by one from the priority queue and removed. They will not affect *dist[]* vector anymore. And thus the queue will be emptied and the algorithm will exit.

### Negative Edge

Please check Dijkstra’s Problem with Negative Edge for further details.