Click here to Skip to main content
Click here to Skip to main content

Non-simple paths in a directed graph.

, 15 Apr 2014 CPOL
Rate this:
Please Sign up or sign in to vote.
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)
   {
             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());
             
            // 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:

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Share

About the Author

Mark Harker

United States 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

Comments and Discussions

 
GeneralPlaying with Fulkerson original code Pinmemberrather_b_sailing16-Apr-14 6:51 
GeneralRe: Playing with Fulkerson original code PinmemberMark Harker16-Apr-14 11:29 
QuestionVery good article Mark! PinprofessionalVolynsky Alex15-Apr-14 23:03 
AnswerRe: Very good article Mark! PinmemberMark Harker16-Apr-14 6:27 
GeneralRe: Very good article Mark! PinprofessionalVolynsky Alex16-Apr-14 6:29 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.

| Advertise | Privacy | Mobile
Web04 | 2.8.141015.1 | Last Updated 15 Apr 2014
Article Copyright 2014 by Mark Harker
Everything else Copyright © CodeProject, 1999-2014
Terms of Service
Layout: fixed | fluid