Posts

Showing posts from May, 2016

Finding the Longest Path From One Point To Another - Dynamic Programming

Image
Hey ! Finding the longest path is one of the most basic applications of a graph and we would always want to find the best solution for this problem. It may be pretty simple to do it manually but when you do it programatically it is kind of difficult. In this program we will be solving the longest path problem using Dynamic Programming (DP).

In this approach we will find all the adjacent nodes of the current node and we will find the longest path from the current node to the destination via the adjacent nodes. So we will be calling the function recursively to find the longest path. Consider the following example.


The longest path from 0 to 4 for the above graph can be calculated as follows :

longest(0 to 4) = max(2 + longest(1 to 4), 3 + longest(2 to 4))

Program


Output

The following is the output of the above shown graph.