# Single Source Shortest Path Algorithm (Given there is a negative cycle in a graph)

suggest change*Before reading this example, it is required to have a brief idea on edge-relaxation. You can learn it from **here*

Bellman-Ford Algorithm is computes the shortest paths from a single source vertex to all of the other vertices in a weighted digraph. Even though it is slower than Dijkstra’s Algorithm, it works in the cases when the weight of the edge is negative and it also finds negative weight cycle in the graph. The problem with Dijkstra’s Algorithm is, if there’s a negative cycle, you keep going through the cycle again and again and keep reducing the distance between two vertices.

The idea of this algorithm is to go through all the edges of this graph one-by-one in some random order. It can be any random order. But you must ensure, if **u-v** (where **u** and **v** are two vertices in a graph) is one of your orders, then there must be an edge from **u** to **v**. Usually it is taken directly from the order of the input given. Again, any random order will work.

After selecting the order, we will *relax* the edges according to the relaxation formula. For a given edge **u-v** going from **u** to **v** the relaxation formula is:

if distance[u] + cost[u][v] < d[v] d[v] = d[u] + cost[u][v]

That is, if the distance from **source** to any vertex **u** + the weight of the **edge u-v** is less than the distance from **source** to another vertex **v**, we update the distance from **source** to **v**. We need to *relax* the edges at most **(V-1)** times where **V** is the number of edges in the graph. Why **(V-1)** you ask? We’ll explain it in another example. Also we are going to keep track of the parent vertex of any vertex, that is when we relax an edge, we will set:

parent[v] = u

It means we’ve found another shorter path to reach **v** via **u**. We will need this later to print the shortest path from **source** to the destined vertex.

Let’s look at an example. We have a graph:

We have selected **1** as the **source** vertex. We want to find out the shortest path from the **source** to all other vertices.

At first, **d[1] = 0** because it is the source. And rest are *infinity*, because we don’t know their distance yet.

We will relax the edges in this sequence:

+--------+--------+--------+--------+--------+--------+--------+ | Serial | 1 | 2 | 3 | 4 | 5 | 6 | +--------+--------+--------+--------+--------+--------+--------+ | Edge | 4->5 | 3->4 | 1->3 | 1->4 | 4->6 | 2->3 | +--------+--------+--------+--------+--------+--------+--------+

You can take any sequence you want. If we *relax* the edges once, what do we get? We get the distance from **source** to all other vertices of the path that uses at most 1 edge. Now let’s relax the edges and update the values of **d[]**. We get:

**d[4]**+**cost[4][5]**=**infinity**+**7**=**infinity**. We can’t update this one.**d[2]**+**cost[3][4]**=**infinity**. We can’t update this one.**d[1]**+**cost[1][2]**=**0**+**2**=**2**<**d[2]**. So**d[2]**=**2**. Also**parent[2] = 1**.**d[1]**+**cost[1][4]**=**4**. So**d[4] = 4**<**d[4]**.**parent[4]**=**1**.**d[4]**+**cost[4][6]**=**9**.**d[6]**=**9**<**d[6]**.**parent[6]**=**4**.**d[2]**+**cost[2][2]**=**infinity**. We can’t update this one.

We couldn’t update some vertices, because the `d[u] + cost[u][v] < d[v]`

condition didn’t match. As we have said before, we found the paths from **source** to other nodes using maximum 1 edge.

Our second iteration will provide us with the path using 2 nodes. We get:

**d[4]**+**cost[4][5]**=**12**<**d[5]**.**d[5]**=**12**.**parent[5]**=**4**.**d[3]**+**cost[3][4]**=**1**<**d[4]**.**d[4]**=**1**.**parent[4]**=**3**.**d[3]**remains unchanged.**d[4]**remains unchanged.**d[4]**+**cost[4][6]**=**6**<**d[6]**.**d[6]**=**6**.**parent[6]**=**4**.**d[3]**remains unchanged.

Our graph will look like:

Our 3rd iteration will only update **vertex 5**, where **d[5]** will be **8**. Our graph will look like:

After this no matter how many iterations we do, we’ll have the same distances. So we will keep a flag that checks if any update takes place or not. If it doesn’t, we’ll simply break the loop. Our pseudo-code will be:

Procedure Bellman-Ford(Graph, source): n := number of vertices in Graph for i from 1 to n d[i] := infinity parent[i] := NULL end for d[source] := 0 for i from 1 to n-1 flag := false for all edges from (u,v) in Graph if d[u] + cost[u][v] < d[v] d[v] := d[u] + cost[u][v] parent[v] := u flag := true end if end for if flag == false break end for Return d

To keep track of negative cycle, we can modify our code using the procedure described here. Our completed pseudo-code will be:

Procedure Bellman-Ford-With-Negative-Cycle-Detection(Graph, source): n := number of vertices in Graph for i from 1 to n d[i] := infinity parent[i] := NULL end for d[source] := 0 for i from 1 to n-1 flag := false for all edges from (u,v) in Graph if d[u] + cost[u][v] < d[v] d[v] := d[u] + cost[u][v] parent[v] := u flag := true end if end for if flag == false break end for for all edges from (u,v) in Graph if d[u] + cost[u][v] < d[v] Return "Negative Cycle Detected" end if end for Return d

**Printing Path:**

To print the shortest path to a vertex, we’ll iterate back to its parent until we find **NULL** and then print the vertices. The pseudo-code will be:

Procedure PathPrinting(u) v := parent[u] if v == NULL return PathPrinting(v) print -> u

**Complexity:**

Since we need to relax the edges maximum **(V-1)** times, the time complexity of this algorithm will be equal to **O(V * E)** where **E** denotes the number of edges, if we use `adjacency list`

to represent the graph. However, if `adjacency matrix`

is used to represent the graph, time complexity will be **O(V^3)**. Reason is we can iterate through all edges in **O(E)** time when `adjacency list`

is used, but it takes **O(V^2)** time when `adjacency matrix`

is used.