Bellman Ford Algorithm

Hello people…! In this post I will talk about another single source shortest path algorithm, the Bellman Ford Algorithm. Unlike Dijkstra’s Algorithm, which works only for a graph positive edge weights, the Bellman Ford Algorithm will give the shortest path from a given vertex for a graph with negative edge weights also. Due to this, the Bellman Ford Algorithm is more versatile, but, it’s speciality comes at a cost. The runtime complexity of Bellman Ford Algorithm is O(|V||E|), which is substantially more than that of Dijkstra’s Algorithm. Sometimes this algorithm is called Bellman Ford Moore Algorithm, as the same algorithm was published by another researcher.

Before we get started, there are a couple of things that we must understand. Firstly, why does Dijkstra’s Algorithm fail for negative edge weights and second, the concept of Negative Cycles.

Why does Dijkstra fail?

Consider, the graph below,

Negative Edges in a Graph

Negative Edges in a Graph

The Dijkstra’s Algorithm is based on the principle that, if S → V1 → … → Vk is the shortest path from S → Vk then D(S, Vi) ≤ D(S, Vj). But in the above given graph, clearly that principle is violated. In the above graph, the shortest path from V1 to V3 is of length 3 units but the shortest path to V4 is of length 1 unit which means that V4 is actually closer to V1 than V3, which is contradicting Dijkstra’s principle.

Negative Cycles

A Negative Cycle is a path V1 → V 2 → V3 → … Vk → V1 where the total sum of the edge weights in the path is negative. Consider the graph below –

Negative Cycle in a Graph

Negative Cycle in a Graph

The path B → C → D is a negative cycle as the path’s total weight would be -2. So, the distance from A → B is 2, but if we circle the cycle once, we would get the distance as 0, if we circle once more, we would get -2. Like this we could keep on circling as much as we want to reduce the shortest distance. Hence the shortest distance to the vertex B, E becomes indeterminate.

So, we want Bellman Ford Algorithm to solve these two issues. We want it to compute the shortest path even for a graph with negative edges and negative cycles. The Bellman Ford will accurately compute the shortest path for a graph with negative edges but the algorithm fails for a graph with negative cycles. But, the algorithm can tell you if a negative cycle exists or not. If it exists the solution it puts up is incorrect, otherwise, the solution given by Bellman Ford Algorithm is perfect. This sounds fine because logically there will be no shortest paths for a graph with negative cycles.

Unlike the Dijkstra’s Algorithm where we had to use a priority queue, we will require no additional data structure to code Bellman Ford Algorithm. This makes writing the code much easier. And the algorithm is pretty straight-forward too. Take a look at the pseudo-code of the Bellman Ford Algorithm given below –

bellmanFord(G, s)
	for all edges in G(V)
		D(V) = INT_MAX
		parent[V] = -1

	D(s) = 0

	for i = 1 to |G(V)| - 1
		for each edge (u, v) in G(E)
			if edge can be Relaxed
				D(v) = D(u) + weight of edge (u, v)
				parent[v] = u

	for each edge in G(E)
		if edge can be Relaxed
			return false

	return true

You may not understand the pseudo-code at the first look, here’s a step-by-step representation of it –

  • Initialise the array which contains the shortest distances to infinity (a high integer value in the pseudo-code).
  • Initialise the parent array which contains the parent vertices in the shortest path to NULL (or -1 if it is an integer array).
  • Set the shortest distance of starting vertex to 0.
  • Explore all the edges, and see if you can relax them. If you can, relax the edge and proceed with the exploration.
  • Do the above operation |V| – 1 times.
  • After that, do another exploration on the graph checking all the edges if they can be relaxed. If they can be relaxed, you can a negative cycle in the graph. Hence, return false.
  • If the exploration gets finished successfully, the graph has no negative cycles and the data that you compute dis correct, so return true.

Now, what does exploring all the edges mean? If you are implementing the graph using an Adjacency List, it means to iterate over all the linked lists associated with all vertices. Now, what will be the sum of all the nodes in all Linked Lists in a given Adjacency List? Number of edges off course! So, we check all the edges from, edges of vertex 1 to vertex |V| in a linear manner. This whole operation takes O(|E|) time, which is repeated |V| – 1, so this part of the code takes O(|E||V|) time. Now, analyse the pseudo-code for a few minutes. Ask yourself how would you code this-ans-that. Now, when your mind is filled with the pseudo-code, look at the sketch below. The sketch below is sort of, “dry run” of the pseudo-code stated above –

Bellman Ford Algorithm Step-by-Step

Bellman Ford Algorithm Step-by-Step

The above sketch is self-explanatory. I hope you understand how the iterations go. In a way it looks like a very ordinary algorithm, without any greedy steps or partitions or so. The Bellman Ford Algorithm is pretty easy to code too. If you can work hard for an hour or two I’m sure you can code this algorithm. It does not require any priority queue or other tools. All you need to code Bellman Ford Algorithm is the pseudo-code. The pseudo-code is very important. Keep looking at the pseudo-code again-and-again whenever you get a doubt. I have put my code below for a reference, it is a C++ code –

    

If you have any doubts regarding the algorithm feel free to drop a comment. I’ll surely reply to them. I hope my post helped you in learning the Bellman Ford Algorithm. If it did, let me know by commenting! Keep practising… Happy Coding…! 🙂

Dijkstra’s Algorithm

Hello, people…! In this post, I will talk about one of the fastest single source shortest path algorithms, which is, the Dijkstra’s Algorithm. The Dijkstra’s Algorithm works on a weighted graph with non-negative edge weights and gives a Shortest Path Tree. It is a greedy algorithm, which sort of mimics the working of breadth first search and depth first search.

The Dijkstra’s Algorithm starts with a source vertex ‘s‘ and explores the whole graph. We will use the following elements to compute the shortest paths –

  • Priority Queue Q.
  • An array D, which keeps the record of the total distance from starting vertex s to all other vertices.

Just like the other graph search algorithms, Dijkstra’s Algorithm is best understood by listing out the algorithm in a step-by-step process –

  • The Initialisation –
  1. D[s], which is the shortest distance to s is set to 0. The distance from the source to itself is 0.
  2. For all the other vertices V, D[V] is set to infinity as we do not have a path yet to them, so we simply say that the distance to them is infinity.
  3. The Priority Queue Q, is constructed which is initially holds all the vertices of the graph. Each vertex V will have the priority D[V].
  • The Algorithm –
  1. Now, pick up the minimum priority (D[V]) element from Q (which removes it from Q). For the first time, this operation would obviously give s.
  2. For all the vertices, v, adjacent to s, i.e., check if the edge from s → v gives a shorter path. This is done by checking the following condition –

    if, D[s] + (weight of edge s → v) < D[v], we found a new shorter route, so update D[v]
    D[v] = D[s] + (weight of edge s → v)

  3. Now pick the next minimum priority element from Q, and repeat the process until there are no elements left in Q.

Let us understand this with the help of an example. Consider the graph below –

Dijkstra's Algorithm - Theory of ProgrammingFirstly, initialize your components, the shortest distances array D, the priority queue Q. The distance from the source to itself is zero. So, D[s] = 0, and the rest of the array is ∞. The set of vertices is inserted into the priority queue Q, with a priority D[v]. Now, we start our algorithm by extracting the minimum element from the priority queue.

Dijkstra's Algorithm - Theory of Programming

The minimum element in the priority queue will definitely be s (which is A here). Look at all the adjacent vertices of A. Vertices B, C, D are adjacent to A. We can go to B travelling the edge of weight 2, to C travelling an edge of weight 1, to D travelling an edge of weight 5. The values of D[B], D[C], D[D] are ∞ . We have found a new way of reaching them in 2, 1, 5 units respectively, which is less than ∞, hence a shorter path. This is what the if-condition mentioned above does. So, we update the values of D[B], D[C], D[D] and the priorities of B, C, D, in the priority queue. With this, we have finished processing the vertex A.

Dijkstra's Algorithm - Theory of Programming

Now, the process continues to its next iteration and we extract the minimum element from the priority queue. The minimum element would be vertex C which would be having a priority of 1. Now, look at all the adjacent vertices to C. There’s vertex D. From C, it would take 1 unit of distance to reach D. But to reach C in prior, you need 1 more unit of distance. So, if you go to D, via C, the total distance would be 2 units, which is less than the current value of shortest distance discovered to D, D[D] = 5. So, we reduce the value of D[D] to 2. This reduction is also called as “Relaxation“. With that, we’re done with vertex C.

Dijkstra's Algorithm - Theory of Programming

Now, the process continues to its next iteration and we extract the minimum element from the priority queue. Now, there are two minimum elements, B and D. You can go for anyone. We will go for vertex D. From D, you can go to E and F, with a total distance of 2 + 2 {D[D] + (weight of D → E)}, and 2 + 3. Which is less than ∞, so D[E] becomes 4 and D[F] becomes 5. We’re done with vertex D.

Dijkstra's Algorithm - Theory of Programming

Now, the process continues to its next iteration and we extract the minimum element from the priority queue. The minimum element in the priority queue is vertex B. From vertex B, you can reach F in 2 + 1 units of distance, which is less than the current value of D[F], 5. So, we relax D(F) to 3. From vertex B, you can reach vertex D in 2 + 2 units of distance, which is more than the current value of D(D), 2. This route is not considered as it is clearly proven to be a longer route. With that, we’re done with vertex B.

Dijkstra's Algorithm - Theory of ProgrammingNow, the process continues to its next iteration and we extract the minimum element from the priority queue. The minimum element in the priority queue is vertex E. From vertex E, you can reach vertex C in 4 + 4 units of distance, which is more than the current value of D(C), 1. This route is not considered as it is clearly proven to be a longer route. With that, we’re done with vertex E.

Dijkstra's Algorithm - Theory of ProgrammingNow, the process continues to its next iteration and we extract the minimum element from the priority queue. The minimum element in the priority queue is vertex F. You cannot go to any other vertex from vertex F, so, we’re done with vertex F.

Dijkstra's Algorithm - Theory of ProgrammingWith the removal of vertex F, our priority queue becomes empty. So, our algorithm is done…! You can simply return the array D to output the shortest paths.

Having got an idea about the overall working of the Dijkstra’s Algorithm, it’s time to look at the pseudo-code –

dijsktra(G, S)
    D(S) = 0
    Q = G(V)

    while (Q != NULL)
        u = extractMin(Q)
        for all V in adjacencyList[u]
            if (D(u) + weight of edge &amp;lt; D(V))
                D(V) = D(u) + weight of edge
                decreasePriority(Q, V)

In the pseudo-code, G is the input graph and S is the starting vertex. I hope you understand the pseudo-code. If you don’t, feel free to comment your doubts. Now, before we code Dijkstra’s Algorithm, we must first prepare a tool, which is the Priority Queue.

The Priority Queue

The Priority Queue is implemented by a number of data structures such as the Binary Heap, Binomial Heap, Fibonacci Heap, etc. The priority queue in my code is implemented by a simple Binary Min Heap. If you are not aware about the Binary Heap, you can refer to my post on Binary Heaps. Now the functionalities that we need from our priority queue are –

  • Build Heap – O(|V|) procedure to construct the heap data structure.
  • Extract Min – O(log |V|) procedure, where we return the top-most element from the Binary Heap and delete it. Finally, we make the necessary changes to the data structure.
  • Decrease Key – We decrease the priority of an element in the priority queue when we find a shorter path, as known as Relaxation.

If you know the working of the Binary Heap you can code the Priority Queue in about 1-2 hours. Alternatively, you can use C++ STL’s priority queue instead. But you don’t have a “decrease key” method there. So, if you want to use C++ STL’s priority queue, instead of removing elements, you can re-insert the same element with the lowered priority value.

Simple O(|V|2) Implementation

If you choose to implement priority queue simply by using an array, you can achieve the minimum operation in O(N) time. This will give your algorithm a total runtime complexity of O(|V|2). It is the simplest version of Dijkstra’s algorithm. This is the version you are supposed to use if you quickly want to code the Dijkstra’s algorithm for competitive programming, without having to use any fancy data structures. Take a look at the pseudocode again and try to code the algorithm using an array as the priority queue. You can use my code below as a reference –

CJava
    
    

Faster O(|E| log |V|) implementation

You can use a binary heap as a priority queue. But remember that to perform the decrease-key operation, you’ll need to know the index of the vertex inside the binary heap array. For that, you’ll need an additional array to store a vertex’s index. Each time any change is made in the binary heap array, corresponding changes must be made in the auxiliary array. Personally, I don’t like this version but I’ll put my code below so that you can use it as a reference.
If you want to do the same thing in C++, you can use a priority queue to reduce a lot. The tweak here is that because you cannot remove a certain vertex from a C++ STL priority queue, we can re-insert it with the new lower priority. This will increase the memory consumption but trust me, its worth it. I have put the codes for both versions below.

C using Binary HeapC++ using STL
    
    

The complexity of the above codes is actually O(|V| + |E|) ✗ O(log |V|), which finally makes it O(|E| log |V|). Dijkstra’s Algorithm can be improved by using a Fibonacci Heap as a Priority Queue, where the complexity reduces to O(|V| log |V| + |E|). Because the Fibonacci Heap takes constant time for Decrease Key operation. But the Fibonacci Heap is an incredibly advanced and difficult data structure to code. We’ll talk about that implementation later.

This is the Dijkstra’s Algorithm. If you don’t understand anything or if you have any doubts. Feel free to comment them. I really hope my post has helped you in understanding the Dijkstra’s Algorithm. If it did, let me know by commenting. I tried my best to keep it as simple as possible. Keep practising and… Happy Coding…! 🙂

Snakes and Ladders Game Code

Hello people…! In this post, we will discuss about the Snakes and Ladders Game Code, where we find the shortest path to win the Snakes and Ladders game by using the Breadth First Search (BFS) Algorithm. If you don’t know the algorithm, I suggest you read my post on Breadth First Search Algorithm.

Now, Graph Theory has many applications and I love working with things that have real-world applications, well, off course the other data structures too have their uses, but the speciality of Graph Theory is its applications have the closest association with our day-to-day activities. And to show you this and to set an example on how the BFS is actually put into action, I am taking up the example of the very popular game, Snakes and Ladders.

This game needs no introduction. We all must have played it in our childhood. I will explain you, how by using Graphs and BFS we can find the Shortest Path to win the game, and, we will state that path and the number of moves of dice it takes too. Have a good look at the Snakes and Ladder board below, we will be using it as an example throughout this post.

Snakes and Ladders

Snakes and Ladders

You can see we can reach the finish block by an number of ways, but how do you find out the best…? More importantly, how do you put it as code…? That’s what we are going to do. Now, think of how you can represent the game board in terms of a Graph, by Graph I mean in terms of Vertices and Edges.

Don’t be too hard on yourself… Just take the first 7 blocks and try working out on paper what would be the Edge and what would be the Vertices. If you ponder upon this, it is very easy to tell that the numbered blocks on the game board will be our Vertices, then, what will be the Edges…? This depends on how you can go from one block to another on rolling the dice. For now, forget about the ladders and the snakes, just draw the graph for a small portion of the board. It should look somewhat similar to what is in the picture below –

Dice Roll from Block 1

Dice Roll from Block 1

As you see we would have six ways to leave block 1, depending on the dice roll. Same would be the case for block 2, or, block 3, and so on. Now, there is a very important point to be noted here… Remember, this is Directed Graph…! Because, once you roll 5 and go to block 6, there’s no way to come back. So, the directions are important. Now, let us push up the complexity a bit by adding a ladder to our above sketch in block 6, think what would happen to the edges…?

Dice Roll for Block 1 - 5

Dice Roll for Block 1 – 5

If you roll 5 from block 1 you will jump directly to block 27. So is for block 2 when you roll out 4, or, block 3 when you roll out 3 and so on. Now, “logically” speaking, the block 6 does not exists in our graph…! Think about the statement for a while. Whenever you reach block, you are directly jumping to block 27, you don’t stay there. Now, if you were constructing an Adjacency List for this graph…. In the list of adjacent vertices for Vertex 1, would you have Vertex 6 in the list, or Vertex 27…? Vertex 27 of course…! Being at Vertex 6 means being at Vertex 27…!

That is why, our edge arrow did not end at Vertex 6… See it…? One more thing, in your Adjacency List, in the list of adjacent vertices for Vertex 6, what would you have…? Nothing…! Because you cannot come to a situation where you would have to stay on Vertex 6 and roll the dice. So the adjacent nodes list corresponding to Vertex 6 should be empty. These two things are very important, when you implement the Adjacency List for the Snake and Ladder board.

Same would be the case, if a snake was there at a block. Logically that block will not exist as a vertex in our adjacency list, and the corresponding edges must be removed. The only difference being that, the edge created due to a snake can lead you to a block of lower value.

Dice Roll for Block 25

Dice Roll for Block 25

Just to get a better idea of the scenario of a ladder and snake, I have depicted what the Adjacency List would look like for the above two examples shown in the pictures.

Adjustments to the Adjacency List

Adjustments to the Adjacency List

That pic should really clarify all the confusion about the graph. If you still don’t get it, feel free to comment your query…! Now, what do we do once we have the Adjacency List ready…? We just call the Breadth First Search method on that list…! Wait… Really…?! That’s it…? Yes…!

You see the hardest part here in solving the Snakes and Ladder by graphs is correctly determining what your Vertices and Edges are. Once you get that, all you have to do is the Breadth First Search in the resultant graph. Then you can get the shortest path from Vertex 1 to Vertex 100. Now, try getting the Adjacency Lit correct and simply call the BFS method. I’m sure you will succeed if you put in a little dedication. But for those who tried and failed. I have put my code below. Before you look at my code, there are a few logics I have used –

  • In the beginning of the program, I added all the edges as though the Game Board had no snakes or ladders at all (these number of edges is what I printed), then, I removed the respective edges concerning the snakes and ladders one-by-one.
  • When a Vertex ‘n’ has a ladder or a snake, we are supposed to replace the corresponding edges as I depicted in the pictures above, for that, I replaced the Vertex n‘s edge with the new value, in Vertices (n – 1), (n – 2), (n – 3), (n – 4), (n – 5), (n – 6). Because it is only in these vertices that you can find an edge of vertex n.
  • I put all this replacing stuff in a function replace() which takes the Linked List and searches for a value ‘oldVertex’ and replaces it with the value ‘newVertex’ when it finds it.
  • I used an extra element in my array to make them 1 – index based.
  • The number of moves to complete the shortest path would be the level of the last vertex, Vertex 100. Why…?! Think about it for a minute and you’ll get it…!
  • I have added a recursive function, printShortestPath() which recursively looks at the parent of each vertex until the start vertex is reached. It keeps printing vertices as the recursion stack keeps popping out, thus we get the path in a reverse order. Think about this for a while… Trust me… It is easy…! 😉
    

If you can solve this problem, then you can solve Snakes and Ladders: The Quickest Way Up problem of HackerRank. You can think of extending this to a 20 ✗ 20 Snakes and Ladder board or an nn board. You just have to add n2 edges to the graph. Solving puzzles by Graph Theory is real fun. I hope this post helped you. If you have any doubts, feel free to comment them. Keep practicing… and… Happy Coding…! 🙂