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. Solution: 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.