Introduction
In this article I would like to discuss how you can find all non-simple paths from a starting node to an end node in a directed graph. Non-simple path is a path that can include cycles and can have the edges with negative weight. The solution to the classic version of the problem that is about finding all simple paths between two arbitrary nodes in a directed graph is well - known and there are many examples of how to do this; however, I could not find anything helpful about how to find paths that are not simple. So, I decided to put together this article to demonstrate how can you tackle the problem.
To make the article more interesting, I will use a programming puzzle to show how can you solve the non-simple paths problem.
Puzzle:
A cab driver needs to find a route from one city to another
without running out of gas. Between each pair of cities are possible clients
ready to pay for a drive, allowing the cab driver to accumulate a certain
amount of money each time it travels from one city to another. Some routes charge a toll, resulting in losing
a certain amount of money. You have to compute a route maximizing
the profit. Your program takes the name of the starting city, the name of the
destination city, the distance between them and the possible profit from a
route.
Example:
Assume that we have the following connections:
A --------->B distance: 10 profit: 40
B --------->C distance: 15 profit: 5
C --------->B distance: 15 profit: 30
A --------->C distance: 30 profit: 50
If cab driver has gas for 40 miles and travels from A to C,
the best trip is A -> B -> C -> B -> C with profit 55.
As you see, it is a complex problem: the paths have to
maximize profit, can include
cycles, can visit the end node more than
one time and can have negative weight. It is obvious that
such algorithms as Dijkstra's or Bellman-Ford will not work here; also, it is obvious that it cannot be solved
in exactly the same way as the problem
with finding a simple connections between two arbitrary nodes.
Solution:
What we want to do is find all the possible paths going from
point A to point B that don't exceed a specified distance. Although there can
be cycles involved and the end node can be visited more than once, the distance
limitation allows us to enumerate them all, since each of them is
uniquely identified by its length. In other words, the atomicity of the paths
is determined not simply by the starting and ending points but also by
their length.
In order to get all the paths starting from point A, we are
going to traverse the graph using depth-first search that begins at the point
A. While going through a child, we are
going to make a link child -> parent in order to know all the edges we have
already visited. Before we go to that
child, we must traverse that linked list and make sure the specified edges are
in acceptable distance limit. When we
arrive to the destination point that is in the distance limit, we can store the
path we found. If the distance limit is exceeded, the search begins tracing
back to find the next path.
private void Search(Graph g, LinkedList<int> visited)
{
var nodes = g.Adj(visited.Last.Value);
foreach (var edge in nodes)
{
if (_pathDistance + edge.Distance > _maxDistance)
continue;
int w = edge.To;
if (w == _target)
{
visited.AddLast(w);
_pathDistance += edge.Distance;
_pathProfit += edge.Profit;
SavePath(visited);
Print(visited);
visited.RemoveLast();
_pathDistance -= edge.Distance;
_pathProfit -= edge.Profit;
}
}
foreach (var edge in nodes)
{
if (_pathDistance + edge.Distance > _maxDistance)
{
continue;
}
int w = edge.To;
visited.AddLast(w);
_pathDistance += edge.Distance;
_pathProfit += edge.Profit;
Search(g, visited);
visited.RemoveLast();
_pathDistance -= edge.Distance;
_pathProfit -= edge.Profit;
}
}
As you can see, the
solution to the problem is a depth-first search that finds all the paths between
the two vertices that don't exceed the specified max distance between them. The
end of a path is not determined simply by hitting the destination node but by
distance that can be covered during a trip. The search keeps the track of the amount
of profit gained during the traversal. In the result, each selected path is associated
with its total weight.
When we know all the possible connection, we can find which
one is the most profitable. To accomplish these we store the paths in priority
queue.
private void SavePath(LinkedList<int> visited)
{
_paths.Add(visited.ToArray());
_pq.Add(new State(_paths.Count() - 1, _pathProfit, _pathDistance ));
}
Now, we can query the queue to find the most optimal connection.
public double BestProfit()
{
return _pq.FindMax().Profit;
}
Example:
We feed our program with the following connections:
start
end
distance profit
Alicetown Bobville 10 50
Alicetown Carolina 30 60
Bobville Carolina 15 5
Carolina Bobville 15 5
Bobville Danburg 20 75
Danburg Bobville 20 40
Bobville Eveland 25 15
Carolina Danburg 10 20
Carolina Eveland 30 20
Danburg Eveland 40 40
Eveland Danburg 20 40
Eveland Frank
City 15 -10
Frank
City Danburg 10 35
Then, we request the following trips: