2
\$\begingroup\$

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

Rules

  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!

\$\endgroup\$
  • \$\begingroup\$ Clarification: Do we have to go through the shortest-path nodes in the correct order? Also, are edge weights guaranteed positive? \$\endgroup\$ – isaacg Jul 1 '14 at 0:40
  • 3
    \$\begingroup\$ I'm pretty sure finding the optimal solution is NP-complete for the same reason Longest Path is. Just reduce from Hamiltonian Path. So, any algorithm is going to be exponential. Moreover, since the reduction doesn't require any blowup, no algorithm can be faster than one for Hamiltonian path, for which the best deterministic algorithm I'm aware of is O(n^2 2^n) \$\endgroup\$ – xnor Jul 1 '14 at 2:11
  • 1
    \$\begingroup\$ On several edges in your example you gave more than one weight, e.g. B-C has weights 5 and/or 3 without an additional vertex between. \$\endgroup\$ – Howard Jul 1 '14 at 4:39
  • \$\begingroup\$ @xnor is that a problem? \$\endgroup\$ – Martin Ender Jul 1 '14 at 7:13
  • 1
    \$\begingroup\$ @cagirici "clearly"? No, that is by no means implied by any of the tags you used. Neither is it a common default tie-breaker employed on PPCG. If you want to use votes as the tie breaker, you should specify that in the challenge. \$\endgroup\$ – Martin Ender Jul 1 '14 at 9:21
4
\$\begingroup\$

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:

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

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

  3. Now, use dynamic programming to solve the traveling salesman problem on this new graph as follows:
  4. 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.
  5. Initialize the memo table with the entry m[(source,{source}]=0, p[(source,{source}]=None.
  6. 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.
  7. Using the completed memo table, find the minimum value of m[(destination,S)], for all subsets S of the input vertices.
  8. 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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.