5 of 5 edited tags

Racketeer Taxi Driver

The Scenario

You are a taxi driver in your city. You picked up a passenger from the airport and he told you the place he'd like to go.

To earn more money, you need to drive as much as you can. However, there are two problems:

  • He always looks around. Therefore, you cannot pass from the same district twice.
  • The passenger is not so dumb. He knows the shortest way between the airport and the destination. Therefore, while you're driving, you should pass each of those districts.

The Input

Input is an undirected and edge weighted graph. The vertices are the districts and the edges are the ways that connect those districts. The weights of the edges indicate the distance between the districts. You can model the graph any way you want.

The Output

Given the source and destination, among with the shortest path, find the longest path that contains each vertex in the shortest path.

The Example

An example graph WHOOPS there are two different edge weights between B and C.
Source: A
Destination: K
Shortest Path: A-D-F-I-K
Solution: A-B-C-D-E-F-G-H-I-J-K


  1. Your solution should be generic and can be applicable to all kinds of connected graphs.
  2. No cycles are allowed. You can pass through a vertex only once
  3. Brute-force is not allowed. Don't list all the possibilities and pick among them.
  4. The edge weights are always positive.
  5. It is a must to visit all vertices in the shortest path, however, the order is not important.

Duration: 1 week.
Tie breaker: Votes.
The code with the least run-time complexity (in terms of Big-O notation) wins!