15,042,389 members
Articles / General Programming / Algorithms
Article
Posted 15 Apr 2014

16.4K views
20 bookmarked

Non-simple paths in a directed graph.

Rate me:
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.

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)
{
foreach (var edge in nodes)
{
if (_pathDistance + edge.Distance > _maxDistance)
continue;

int w = edge.To;
if (w  == _target)
{
_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;
_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)
{

// priority queue
_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:

Share

 United States
Software Developer with more than 15 years of experience.
Developed apps using VB, Java and Delphi; during the last nine years my main focus was on C# and .Net.

Recognitions:
Microsoft Certified Application Developer
Microsoft Certified Solution Developer
Microsoft Certified Professional
Sun Certified Programmer for the Java 2 Platform

 First Prev Next
 Playing with Fulkerson original code Midnight48916-Apr-14 6:51 Midnight489 16-Apr-14 6:51
 Some thoughts come to mind: try the original min cost max flow labeling algorithm that was made famous by Ford and Fulkerson. Although any combinatorial class will discuss more recent advances and optimizations, the original data set is easy to work with: from-node to-node min-flow max-flow unit-cost Variations of the problem you present: reverse the sign of all the costs and set min flow to 0 and max flow to number of "to-nodes" (perhaps add node flow control arcs); or, if total cost path order is not required, assign a cost of -1 instead of actual costs also paying attention to max flow capacities. Thanks for reminding me of directed paths and problem solving.
 Re: Playing with Fulkerson original code Mark Harker16-Apr-14 11:29 Mark Harker 16-Apr-14 11:29
 Very good article Mark! Volynsky Alex15-Apr-14 23:03 Volynsky Alex 15-Apr-14 23:03
 Re: Very good article Mark! Mark Harker16-Apr-14 6:27 Mark Harker 16-Apr-14 6:27
 Re: Very good article Mark! Volynsky Alex16-Apr-14 6:29 Volynsky Alex 16-Apr-14 6:29
 Last Visit: 31-Dec-99 18:00     Last Update: 28-Sep-21 7:25 Refresh 1