Problem: Given a weighted directed graph, find the shortest path from a given source to a given destination vertex using the Bellman-Ford algorithm.

shortest path in weighted directed graph

In the previous post, we learned to calculate the distance of vertices by applying the Bellman-Ford algorithm, did not find the leading path to them.

We can keep track of the path from the source to all other vertices by storing the reference of the preceding vertices.

Relaxing edges in Bellman Ford algorithm

Whenever we relax any edge, we also update the preceding vertex of the target vertex.

By tracing the preceding references, we print the path from the destination to the source node in reverse order.

Here is the implementation of the solution in Python, Java and C++:

Python

C++

Java

Output:

Distance: 20
Path: [A, B, C, D, E]


In this example, we have chosen A as the source vertex and E as the destination vertex.

In the above program, we have represented graph as a adjacency list.

We first created the list of vertices and edges of the given graph and then executed the Bellman-Ford algorithm on it.

After the execution of the algorithm, we traced the path from the destination to the source vertex and output the same.

The complexity of the algorithm is O(VE). Since this solution incorporates the Belman-Ford algorithm to find the shortest path, it also works with graphs having negative-weighted edges.

Leave a Reply

two × 2 =