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))



 The following is the output of the above shown graph.


Popular posts from this blog

Finding the Longest Palindrome in a String

Finding a Single Number amongst Repeated Numbers [Repeated Twice]