Since I had been dealing with Graphs for the past few months, So I thought of writing something basic rather than some new shiny thing. In this post we will take a look at Dijkstra, Pseudocode and code. As we all know that Dijkstra is a shortest path algorithm which is used by OSPF and IS-IS. In general, that’s the extent most people care about Dijkstra and rightly so, as all the complexity is hidden from the user and stuff just works, so they don’t need to know the details. But just in case you do care about having strong fundamentals and having an understanding how things works, this post may be for you. I will try my best to keep things simple and in line with what Dijkstra said:

“Simplicity is a great virtue but it requires hard work to achieve it and education to appreciate it. And to make matters worse: complexity sells better.” — Dijkstra

**1.0 Setting the stage (It’s all about Graphs):**

**Graphs: **

Many computational applications naturally involve not just a set of items, but also a set of connections between pairs of those items. The relationships implied by these connections lead immediately to a host of natural questions like is there a way to get from one item to another by following the connections? How many other items can be reached from a given item? What is the best way to get from this item to another item?

Example of computational applications can be maps, social networks, circuits, computer networks.

To model such situations, we can use abstract objects called **Graphs** (In simple words when I say Graph, it is an abstract data type which means that they aren’t available as an inbuilt data structure in a given language and one has to use some other data structure to represent Graphs). In below fig. 1, a network with routers, P, Q, R, S, T and the links between them can be represented diagrammatically by means of points and lines. The points P, Q, R, S, T is called vertices, the lines are called edges, and the whole diagram is called a **Graph**.

Fig. 1

So a graph G= (V, E) is defined by a set of vertices, V, plus a set of edges E, over pairs of these vertices. There are essentially three types of graphs:

- Undirected, unweighted graphs
- An undirected, unweighted graph models a relationship between vertices (p, q) without regard to the direction of the relationship. For instance below is an edge (p, q) which represents that P is connected to the Q and vice versa. Also the edge (p, q) doesn’t have any weight associated with it. In networking terms, weight will be equivalent of the metric / cost of a link. Obviously this doesn’t sound the right way to represent the networks as we have cost on the links and they can be asymmetric.

Fig.2

- Directed graphs
- In the case of Directed graphs, edges are ordered pairs – the order between two vertices the edges connect is important. For instance (p, q) models the relationship between vertices p–>q, and (q,p) models the relationship q–>p. In the below fig. first graph represents (p, q) and there is no edge from q–>p, second Graph contains two edges (p, q) and (q, p) representing connectivity p–>q and q–>p. One way traffic roads are one suitable example directed graphs.

Fig.3

- Weighted graphs
- These graphs essentially model graphs where there is a numeric value associated with edges representing relationship between vertices (p,q). So for instance in the below directed graph, we have weight associated with the edges. (p,q) = 10 and (q,p) = 5. Now this looks more like a right way to represents the network, we have metrics/cost associated with the links which can be asymmetric.

Fig.4

So from here on we will be using — Directed, Weighted type of graph to represent our network.

2.0 How are Graphs represented?

If you remember I mentioned earlier that Graphs are abstract data types and now we will take a peak at some common ways to represent a graph. We will use below sample network as an example where all the blue links has a Cost 10 bidirectional and Red links has Cost 20 bidirectional.

Fig. 5

**2.1 Adjacency Matrix:**

So one way is to use a N x N two-dimensional matrix to represent the graph where N is the number of Nodes. The value stored in the cell at the intersection of row V and column N indicates the cost. As you can see [R5,R3] and [R3,R5] has cost of 20 and every other cell value has cost of 10. An empty cell means no link between given nodes.

R1 | R2 | R3 | R4 | R5 | |

R1 | 10 | 10 | |||

R2 | 10 | 10 | |||

R3 | 10 | 10 | 20 | ||

R4 | 10 | 10 | 10 | ||

R5 | 20 |

Pretty easy, huh?. Let’s take a look at some pros and cons with representation:

Pros:

- Simple way to represent a graph.
- Worst case for accessing a specific edge (u,v) is in constant time ? In simple words, doesn’t matter how big our graph (network) becomes, accessing an edge for a pair is constant which is a good thing.
- Optimal structure for Full mesh graphs where each node is connected to every other node.

Cons:

- Inefficient way to represent sparse networks which are more realistic. As you can see that many cells are empty which means we will be wasting memory. If you want a fancy way of saying that then what I meant was that it adjacency matrix uses ?space which means a lot of space.
- If you look at our example, we have 25 (5 x 5) memory cells out of which 11 are filled and 14 cells are empty i.e 56% of empty spaces.

**2.2 Adjacency list:**

So this representation is more efficient then Adjacency matrix representation. In this we keep a master list of all the vertices (nodes) and each vertex (node) keeps an array or linked list of other vertices(nodes)/cost to whom they are neighbor. For instance:

Fig. 6

In this representation space requirement for storing information is where n is the number of vertices and m is the number of edges. As an example just to have an idea, we need to have 5+12 where 5 is the nodes and if you count the total number of lists for each of the 5 nodes its 12 to represent fig.5 . So you can see its more efficient to store sparse graphs compared to Matrix representation.

**Cons:** The cons with this representation here is that for certain operation, it may take more time for instance getting a specific edge between two nodes like (u,v), we have to go to that Node in the master list and then traverse the list to see if that edge exists compared to matrix representation where it takes a constant time to do this operation.

Few other ways to represent that are ** Edge List** and

**but I will leave that as an exercise to the reader.**

*Adjacency Map***3.0 Priority Queue:**

Before we dig into Dijkstra Algorithm, I want to cover another basic entity called Priority Queues which will be used by Dijkstra implementation. Like in a real life Queue, it allows to add elements to the end of the list and removes the element from the front of the list, however in the case of Priority Queue the logical order is determined by the Priority of the items in the queue. Highest Priority items are in front of the queue and lowest are in the back and the middle is arranged accordingly from Highest to lowest priority order. For instance, assume that there are a bunch of people who are waiting to board an Air Plane, and they all are aligned according to their seat numbers assigned to them in the Queue. The guy who has the first Seat Number in the ticket is in the front of the Queue and the guy with the Last seat number is at the end of the Queue. Suddenly few more people show up at the Boarding area and they may have seat numbers assigned to them, which may put them in the front, middle or last of the already existing queue. So rather than putting these people at the end of the queue, we re-arrange the Queue according to the seat Numbers they have to make sure the Property of the Queue is maintained i.e. The guy with the first seat number is in the front and the other guys behind him are aligned accordingly to their seat Number.

Fig.7

Now in our problem scope of Path Computation, a Node with the shortest distance will have the Highest priority and will be in the front of the Queue and the one with largest distance will be at the end of the Queue.

**3.1 Priority Queue (PQ) Implementation:**

Now the next question is how can we implement a Priority Queue. In our example, we will be using Min-Heaps to represent a Priority Queue.

First of all what is a heap? Heaps are binary trees which satisfies the heap property i.e. All nodes are either greater than or equal to (known as Max heap) or less than or equal (Known as Min heap) to each of their children. In this post, we will be looking at Min-Heaps where a node is smaller than their children’s. For example in below Fig.8, Root Node “2” is smaller than both left (4) and right (3) children and so on.

In a Min-Heap, The Root Node is always the smallest node. So in our scope of path computation, the guy with the lowest distance will always be the Root Node and whenever we have to find the next lowest distance element (Highest Priority), we will just refer to the Root Node.

Now if you recall how I mentioned the example of people boarding a plan in the Priority Queue section, that few more people arrived which caused us to re-arrange the Queue. Similarly, we have to make sure that we always maintain the Min-Heap Property i.e. Every node is smaller than its child nodes. In order to do that, there are operations like bubble-up (when we insert a Node) and bubble-down (when we delete a node) are used. I won’t go much into implementation detail and will leave these fundamentals as user exercise except bubble-down.

Now let’s briefly take a look at the process (bubble-down) of maintaining the min-heap property when we remove the minimum element (Root Node) from the Binary Tree. For instance, In the below fig.8, When we remove Root Node (2) from the tree then the Root Node is empty. What we do is then take the last element from the tree i.e. 14 and make it as the Root Node and then perform a bubble-down operations till the Min-Heap property is finished.

- Move the Last node to the Root Node.
- Until the Min-Heap Property is restored:
- Pick the minimum child between Left and Right and compare it with the Root Node.
- If the Root Node is bigger than the Minimum child presented in the previous step then swap.

Fig.8

For Example, if we take the Minimum Element out from the Tree i.e. The Root Node, then we have to restore the min heap property by an operation called bubble-down:

Fig.9

Average and Worst case run time complexity of Delete operation in Min Heaps is O(log n)

**4.0 Problem Statement For Dijkstra:**

The problem statement is simple here, Given nodes (Source, Destination) find the shortest path from Source to Destination or Given a node S (Source), find the shortest path from S (Source) to all other nodes.

**Constraint: **The length or Distance should be non-negative. Dijkstra can not compute shortest path for -ve distances but that’s fine for networks as in reality we don’t have a -ve distance on the networks.

So suppose that we have this backbone network and we want to calculate the shortest path between SEA to MIA. All the links have cost=10, except the thick edges which has link cost of 100. So you can see the Shortest path actually is

SEA –> SJC –> KCY –> WDC –> MIA (cost 40) and we will see next on how Dijkstra as an algorithm will derive this.

Fig.10

**5.0 Dijkstra:**

**“Simplicity is prerequisite for reliability.” — Dijkstra**

IMHO, Once you really understand the algorithm, you will see how the above statement is true for Dijkstra SPF and appreciate its simplicity. Now Dijkstra is an iterative algorithm that provides us the shortest path from one particular node (Source) to all the other nodes. It is essentially a greedy Breadth first search(BFS) algorithm. Greedy in the sense that it will pick up the best choice (least cost path) available at each iteration. BFS in the sense that it processes the nodes in the graph in the order of their shortest distance from the Start Vertex (Source Node).

Below is the pseudocode of Dijkstra with Priority Queue implementation with modification in RED to stop the iteration when the Current Node is the Target node (Destination).

Source: https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm

1 function Dijkstra(Graph,source,target):

2 dist[source] ← 0 // Initialization

3

4 create vertex set Q

5

6 for each vertex v in Graph:

7 if v ≠ source

8 dist[v] ← INFINITY // Unknown distance from source to v

9 prev[v] ← UNDEFINED // Predecessor of v

10

11 Q.add_with_priority(v, dist[v])

12

13

14 while Q is not empty: // The main loop

15 u ← Q.extract_min() // Remove and return best vertex

16 if u == target then break // Exit if the Current Node is Target Node.

17 for each neighbor v of u: // only v that is still in Q

18 alt = dist[u] + length(u, v)

19 if alt < dist[v]

20 dist[v] ← alt

21 prev[v] ← u

22 Q.decrease_priority(v, alt)

23

24 return dist[], prev[]

At a high Level these are the steps taken by Dijkstra:

**Step 0 (Initialization)** : We assign all the nodes a distance value. Since we are looking from SEA Node perspective, the distance from SEA to reach SEA is “Zero”. All other nodes are assigned a distance of “Infinity” also represented as “Inf”. Practical implementation will use some very high number to represent “Infinity”. Since we will be using Priority Queue for Dijkstra, we will have our Priority Queue Initialized (Which is implemented with Min-Heap) where SEA has a distance of “0” and everything else has a distance of Infinity. Priority Queue will use lesser distance value as a higher priority which will make **SEA** as the Root Node.

- Below is the code which does the initialization and that’s how the graph will look like. The Grey color node are the ones which we have visited so far and the Green ones are the ones which we haven’t explored yet. Red color nodes are the one which we have discovered as neighbors of the current node.

Fig.11

- Min-Heap Tree after Initialization: goo.gl/qPj2qK (I will not be posting direct pictures to save some space and will summarize few steps which you will see later, otherwise I will be here all day long writing this post. Not to mention that it’s already too long)

Note that we will be tracking Dist (Distance or Cost) as variable which is a property of a Node and that will decide Node’s relative position in the Min-Heap Tree (PQ). We will also be using a Predecessor (Pred) variable which keeps track of the predecessor of a Node through which the smallest distance is known. Predecessor Information will be used at the end to construct the Path Information. Hopefully as you go through the iterations, things will be more clear.

**High Level Next Steps After Initialization : **

14 **while** *Q* is not empty: *// The main loop*

15 *u* ← *Q*.extract_min() *// Remove and return best vertex*

16 if u == target then break // Exit if the Current Node is Target Node.

17 **for each** neighbor *v* of *u*: *// only v that is still in Q*

18 *alt* = dist[*u*] + length(*u*, *v*)

19 **if** *alt* < dist[*v*]

20 dist[*v*] ← *alt*

21 prev[*v*] ← *u*

22 *Q*.decrease_priority(*v*, *alt*)

The above code is essentially saying:

Repeat the below steps until the Min-Heap tree (which we created during initialization) is not empty:

- Extract the Current Root Node from the Min-Heap Tree. That node becomes your current node and we will refer to that node as “u”.
- If the “u” is equal to the “target”(destination) node then exit.
- For each neighbor (referred as “v”) of the current root node “u” :
- If the (distance of the current node) + (distance between the current node and neighbor) < (previously known distance of neighbor) then:
- Make the distance of Neighbor == (distance of Current Node )+ (Distance between Current Node and Neighbor)
- Since we have updated the distance of the Neighbor, we will need to re-adjust the tree to accommodate the position of the Node in the tree with his updated new distance. It’s commonly known as decrease Key operation. Essentially, we are adjusting the tree according to the new distance of the Node so that we maintain the Min-Heap Property.

- If the (distance of the current node) + (distance between the current node and neighbor) < (previously known distance of neighbor) then:

**Step 1 (Iteration 1)**:

- [
*u*←*Q*.extract_min() ]

The first thing we will do is that we will pop out the smallest distance node i.e. The Root Node “SEA” from the tree and make it as the current Node. As we take out the Current Root Node from the tree, the Root Node position becomes empty and we need to do something to maintain the min-heap property of the tree. So if you recall our bubble-down operation which is performed when we delete the Root Node, we will move the last node to the Root Node and do a bubble down operation to maintain the min-heap property. So this is how our Tree will look like https://goo.gl/XDVkyu (At the very left) with SEA Root node gone. If you compare this with the initial Tree, you can see we moved the last node MIA to the Root Node. As all the distances are **“INF**“, Min-Heap Property isn’t violated yet so we are good for now.

- if u
**==**target then**break**: This will be skipped as the Current Root Node is SEA and MIA is our Target Node which aren’t equal. - The Next portion of the code is this which looks at each neighbor of the current node (SEA) which are “POR”, “MIN” and “SJC”

17 for each neighbor v of u:

18 alt = dist[u] + length(u, v)

19 if alt < dist[v]

20 dist[v] ← alt

21 prev[v] ← u

22 Q.decrease_priority(v, alt)

##### For Neighbor : POR

- Distance of the current node “SEA” + (Distance between the current node “SEA” and Neighbor “POR”) < (Previously known distance of the current node neighbor “POR”)
- 0 + 10 = 10 < INF ==> Since 10 is less than “INF”
- We will update the distance to POR as 10, Update the PRED to SEA and perform the decrease key operation to maintain the min-heap property.

We will repeat the same steps for other two neighbors “SJC” and “MIN”. I won’t go into details of the other two neighbors separately, below is the table with the updated DIST value and Predecessor. In the Table

If you see the cost column in “BLUE” then that means “**if** *alt* < dist[*v*]” condition was met and if it didn’t, then its colored as “RED”. Also the current node column contains the node name and its distance from the source node in the bracket.

Fig.12

Now again as you recall that we are using distance as priority to decide where a Node falls into the queue (represented by the Tree). Since we have updated the Distance from **“INF” **to **“10”** for all the three neighbors, we have to update the distance values and reshuffle the tree according to their Priority so that the order of Min-Heap property is maintained. This is where the decrease key operation comes into the picture where it goes and update the distance and reshuffles the tree to make sure the tree is updated accordingly. Just to keep in mind that the decrease key operation will run after each time the distance is updated for a neighbor under the “For loop” i.e. 3 times in this case, one for each of the neighbor but I am just showing up the end result https://goo.gl/XDVkyu [Far Right picture] after all the 3 iterations are complete.

**Step 3 (Iteration 2):**

At this point our first iteration is complete and we will move to the next Iteration as the Tree is not empty. We are going to pick up again the first item in the priority Queue

I.e. Root Node of the Tree (as that has the minimum distance aka the highest priority) and repeat the iteration. It will make the tree look like this https://goo.gl/KcQ6gW as we popped out the SJC (which was the root node from the previous iteration)

Below is the table of the updated Cost, PRED values.

Fig. 13

Below are the iterations with the Min-Heap and Table/Graph for each iteration, which stops when the Current Node == MIA (Destination)

**Iteration 3:**

https://goo.gl/7KHDBI

https://goo.gl/xkTGaT

**Iteration 4: **

https://goo.gl/7KHDBI

https://goo.gl/5HKlsY

**Iteration 5:**

https://goo.gl/JWO4Tb

https://goo.gl/7ng8S7

**Iteration 6:**

https://goo.gl/JWO4Tb

https://goo.gl/5rVBM2

**Iteration 7:**

https://goo.gl/0Jk9aB

https://goo.gl/6psDw9

**Iteration 8:**

https://goo.gl/0Jk9aB

https://goo.gl/Ifj4Pi

**Iteration 9:**

https://goo.gl/nXtSHx

https://goo.gl/9TFZZ0

**Iteration 10:**

https://goo.gl/nXtSHx

https://goo.gl/h1KwsW

**Iteration 11:**

https://goo.gl/w6S543

https://goo.gl/MWXW20

**Iteration 12:**

https://goo.gl/w6S543

https://goo.gl/Vb212r

**Iteration 13:**

https://goo.gl/Md8KIe

https://goo.gl/m2RPQJ

**Iteration 14: **(At this stage, the loop will be broken this condition will be met ” if u == target then break ” i.e. Current Node == “MIA”)

https://goo.gl/6QWBYh

Now the next question is how do we construct the Path from the Source to the Destination as we weren’t keeping track of that anywhere explicitly and that’s where the PRED variable comes in.

So if you trace back from the Target Node [MIA] Predecessor

**MIA [PRED]==> WDC[PRED] ==> KCY [PRED] ==> SJC [PRED] ==> SEA**

Hence the path from the Source to Destination is **SEA ==> SJC ==> KCY ==> WDC ==> MIA**.

You can take a look at the code here and the output https://repl.it/CWFD/0 . If you want, you can play with it as well by changing the source and destination.

https://github.com/Dipsingh/algorithms/blob/master/spf/anotherspf.py

Now if you see, I can modify the algorithm to add my own constraints, for instance, lets say I want to add a constraint to avoid a given node, lets say “KCY” while computing the shortest path between “SEA” and “MIA” and all I have to do is pass that as a constraint and add that as a condition: (equivalent to line no. 17 in the pseudocode)

if newDist<nextVert.getDistance()and **(**currentVert.**id**!**=node_cst**.**id)**:

And you can see the code and the result of the new SPF with constraint here: https://repl.it/CWQp/0

I hope this was informative to you and if not, then well, it is what it is..

**Reference****s:**

http://interactivepython.org/runestone/static/pythonds/index.html

https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm

Data Structures and Algorithms in Python

## Leave a Reply