## 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.

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.

The code

ReplyDelete----------

#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;

}

what if finding the longest path in 3 arrays? for exmaple using this function

ReplyDeleteint solution(int N, int A[], int B[], int C[], int M); where N = integer and M= Integer of the arrays...

How do i approach that because I am solving a problem similar to th example