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

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.

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.