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


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

Rules


Your solution should be generic and can be applicable to all kinds of connected graphs.
No cycles are allowed. You can pass through a vertex only once
Brute-force is not allowed. Don't list all the possibilities and pick among them.
The edge weights are always positive.
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!
Reduction to Traveling Salesman Problem, O(n^2*2^n).

In the above, n is the number of vertices in the graph.

I will give a description of the algorithm for now. Starting with the input graph, carry out the following steps:


Create a new graph with edge weights equal to the negation of the input edge weights. These weights represent the value to the taxi driver of traversing those edges.
Let N be the sum of all of the negative weights in the (new) graph minus 1. Add N to each outgoing edge from a node on the shortest path (as given in the input). This represents the fact that the taxi driver absolutely must cross each vertex in the shortest path.
Now, use dynamic programming to solve the traveling salesman problem on this new graph as follows:
Next, create a memo table, m, with entries that are pairs, (v,S), where v is the final vertex in the (partial) path created so far, and S is a subset of the vertices in the graph. The weight associated with this entry will be the minimum sum of edge weights to reach v after having passed through the vertices in S. Also, maintain a parent pointer.
Initialize the memo table with the entry m[(source,{source}]=0, p[(source,{source}]=None.
Fill in the memo table, using the recursion that m[(v,S)] = min(m[(u,S-{v})]+w[(u,v)] for u in S), where w is the the edge weight dictionary. Create parent pointers accordingly.
Using the completed memo table, find the minimum value of m[(destination,S)], for all subsets S of the input vertices.
Trace the parent pointers from this minimum value backwards until we reach the source node. The resulting path is the solution.


I don't feel like coding that all up, but I believe it is a correct solution. It runs in O(n^2*2^n) time because there are n*2^n entries in the memo table, and each is generated by taking a minimum over no more than n possibilities. All the other work takes far less than that amount of time.

This solves the problem because the traveling salesman path must go through all of the vertices on the shortest path, because skipping one of those vertices results in an increase in the traveling salesman cost of N, which cannot be offset by the negative edge weights in the graph, since N was chosen to be more negative than all of them combined.