Longest path between two nodes in a graph Amazon Problem : C code

Finding longest path between two nodes in a graph

Problem Statement 

Write algorithm/code to find longest path between any two cities. 4X4 matrix was given. If there is no connectivity between two cities then the distance between them was given as -1. Its cyclic graph.

Solution

Finding longest path between two nodes in a graph is an NP Hard problem. So, we should not try to find a polynomial solution to this problem. As you can see the given problem is of very small size. So even brute force is acceptable.

#include<stdio.h>

int longestPath(int node);

int matrix[4][4] = {{0,1,2,3},{1,0,1,1},{2,1,0,5},{3,4,3,0}};

int main()
{
printf("%d",longestPath(0));
}

int longestPath(int node) {

int dist=0,max=0,i;
for(i=node+1;i<4;i++) {
    dist=0;
    if(matrix[node][i]>0) {
        dist+=matrix[node][i];
        dist+=longestPath(node+1);
    }
    if(max<dist)
        max=dist;
}
printf("%d\t",max);
return max;
}

 

Time Complexity 

Let there be n cities. Given starting city as S and destination city as D. We are left with n-2 cities.
There are approximately 2^(n-2) * (n-2)! ways for reaching D from S.
Find length of all these ways and choose the smallest one.



The other problem of finding longest path is "Find longest path between any two nodes of a tree". Click any where on this line to see the problem.

 

 

 If you find this blog somewhat helpful, please share & Keep Visiting...:)