The problem is this:

Given a graph, find the shortest path from a sourcesto a destinationdand back tos. We will call this theshortest path and backproblem, or theshortest round tripproblem.

A naive algorithm is to simply use Dijkstra's algorithm, or any shortest path algorithm, to find a shortest path from

**s**to

**t**, remove its edges from the graph, then find a return path in the new graph. We can easily find examples for which this fails though.

The correct algorithm involves solving the minimum cost maximum flow problem. This is solved quite easily with the Edmonds-Karp algorithm, where the Breadth-First search used to find the shortest augmenting paths at each step is replaced with the Bellman-Ford algorithm.

I'll leave the details as an exercise, but give an algorithm that is easier to understand if you're not too familiar with flow networks. You can use this algorithm to figure out the flow solution, since the two are actually equivalent.

It goes like this (also available on the SO link):

Find a shortest path

**s -> d**with any algorithm that can do this (Dijkstra if no negative costs, Bellman-Ford otherwise);
Replace the edges of this shortest path with directed arcs directed from

Also negate the costs of these arcs. For example, if

**d**towards**s**. For example, if your shortest path is**s -> x -> y -> z -> d**, replace the edge**(s, x)**with the directed arc**x -> s**,**(x, y)**with the directed arc**y -> x**etc.Also negate the costs of these arcs. For example, if

**(x, y)**had cost**c**, the directed arc**y -> x**will have cost**-c**;
Find a shortest path from

**s**to**d**in this new graph. You'll have to use an algorithm that works with negative edges now;
Remove the edges that appear in

**both**of the shortest paths. What you're left with is the cycle you're after.
As an example, consider the following graph.

The first shortest we find is

**1 -> 2 -> 3 -> 4**, of cost**12**. We transform our graph to:
Notice the negated costs. We then find another shortest path in this new graph, which can only be

**1 -> 3 -> 2 -> 4**, of cost**14**.
We have used the edge

**(2, 3)**in both shortest paths, so we ignore it and draw our solution shortest path and back:
Which has total cost

**26**. Notice that if we had applied the naive algorithm, we would have selected**1 -> 4**as the second path, which would have led to a cost of**28**.
You can also solve this problem on UVA, where you can practice your implementation of the algorithm.

## No comments:

## Post a Comment

Keep it technical and related to the subject matter. Personal comments of any kind will be deleted.