Enumerate all paths in a weighted graph from A to B where path length is between C1 and C2

Given two points A and B in a weighted graph, find all paths from A to B where the length of the path is between C1 and C2.

Ideally, each vertex should only be visited once, although this is not a hard requirement. I suppose I could use a heuristic to sort the results of the algorithm to weed out "silly" paths (e.g. a path that just visits the same two nodes over and over again)

I can think of simple brute force algorithms, but are there any more sophisticed algorithms that will make this more efficient? I can imagine as the graph grows this could become expensive.

In the application I am developing, A & B are actually the same point (i.e. the path must return to the start), if that makes any difference.

Note that this is an engineering problem, not a computer science problem, so I can use an algorithm that is fast but not necessarily 100% accurate. i.e. it is ok if it returns most of the possible paths, or if most of the paths returned are within the given length range.

[UPDATE]

This is what I have so far. I have this working on a small graph (30 nodes with around 100 edges). The time required is < 100ms

I am using a directed graph.

I do a depth first search of all possible paths.

• At each new node
  • For each edge leaving the node
    • Reject the edge if the path we have already contains this edge (in other words, never go down the same edge in the same direction twice)
    • Reject the edge if it leads back to the node we just came from (in other words, never double back. This removes a lot of 'silly' paths)
    • Reject the edge if (minimum distance from the end node of the edge to the target node B + the distance travelled so far) > Maximum path length (C2)
    • If the end node of the edge is our target node B:
      • If the path fits within the length criteria, add it to the list of suitable paths.
      • Otherwise reject the edge (in other words, we only ever visit the target node B at the end of the path. It won't be an intermediate point on a 开发者_开发问答path)
    • Otherwise, add the edge to our path and recurse into it's target node

I use Dijkstra to precompute the minimum distance of all nodes to the target node.

I wrote some java code to test the DFS approach I suggested: the code does not check for paths in range, but prints all paths. It should be simple to modify the code to only keep those in range. I also ran some simple tests. It seems to be giving correct results with 10 vertices and 50 edges or so, though I did not find time for any thorough testing. I also ran it for 100 vertices and 1000 edges. It doesn't run out of memory and keeps printing new paths till I kill it, of which there are a lot. This is not surprising for randomly generated dense graphs, but may not be the case for real world graphs, for example where vertex degrees follow a power law (specially with narrow weight ranges. Also, if you are just interested in how path lengths are distributed in a range, you can stop once you have generated a certain number.

The program outputs the following: a) the adjacency list of a randomly generated graph. b) Set of all paths it has found till now.

public class AllPaths {

    int numOfVertices;
    int[] status;
    AllPaths(int numOfVertices){
        this.numOfVertices = numOfVertices;
        status = new int[numOfVertices+1];
    }

    HashMap<Integer,ArrayList<Integer>>adjList = new HashMap<Integer,ArrayList<Integer>>(); 
    class FoundSubpath{
          int pathWeight=0;
          int[] vertices;

        }


    // For each vertex, a a list of all subpaths of length less than UB found.
    HashMap<Integer,ArrayList<FoundSubpath>>allSubpathsFromGivenVertex = new HashMap<Integer,ArrayList<FoundSubpath>>();

    public void printInputGraph(){

        System.out.println("Random Graph Adjacency List:");

        for(int i=1;i<=numOfVertices;i++){
            ArrayList<Integer>toVtcs = adjList.get(new Integer(i));
            System.out.print(i+ " ");
            if(toVtcs==null){
                continue;
            }
            for(int j=0;j<toVtcs.size();j++){
                System.out.print(toVtcs.get(j)+ " ");
            }
            System.out.println(" ");
        }

    }

    public void randomlyGenerateGraph(int numOfTrials){

        Random rnd = new Random();

        for(int i=1;i < numOfTrials;i++){
            Integer fromVtx = new Integer(rnd.nextInt(numOfVertices)+1);
            Integer toVtx = new Integer(rnd.nextInt(numOfVertices)+1);
            if(fromVtx.equals(toVtx)){
                continue;
            }
            ArrayList<Integer>toVtcs = adjList.get(fromVtx);
            boolean alreadyAdded = false;
            if(toVtcs==null){
                toVtcs = new ArrayList<Integer>();
            }else{
                for(int j=0;j<toVtcs.size();j++){
                    if(toVtcs.get(j).equals(toVtx)){
                        alreadyAdded = true;
                        break;
                    }
                }
            }
            if(!alreadyAdded){
            toVtcs.add(toVtx);
            adjList.put(fromVtx, toVtcs);
            }
        }

    }

    public void addAllViableSubpathsToMap(ArrayList<Integer>VerticesTillNowInPath){
        FoundSubpath foundSpObj;
        ArrayList<FoundSubpath>foundPathsList;
        for(int i=0;i<VerticesTillNowInPath.size()-1;i++){
                Integer startVtx = VerticesTillNowInPath.get(i);
            if(allSubpathsFromGivenVertex.containsKey(startVtx)){
                foundPathsList = allSubpathsFromGivenVertex.get(startVtx);
            }else{
                foundPathsList = new ArrayList<FoundSubpath>(); 
            }

            foundSpObj = new FoundSubpath(); 
            foundSpObj.vertices = new int[VerticesTillNowInPath.size()-i-1];
            int cntr = 0;
            for(int j=i+1;j<VerticesTillNowInPath.size();j++){
                foundSpObj.vertices[cntr++] = VerticesTillNowInPath.get(j);
            }
            foundPathsList.add(foundSpObj);
            allSubpathsFromGivenVertex.put(startVtx,foundPathsList);
        }

    }

    public void printViablePaths(Integer v,ArrayList<Integer>VerticesTillNowInPath){

        ArrayList<FoundSubpath>foundPathsList;
        foundPathsList = allSubpathsFromGivenVertex.get(v);

        if(foundPathsList==null){
            return;
        }

            for(int j=0;j<foundPathsList.size();j++){
                for(int i=0;i<VerticesTillNowInPath.size();i++){
                    System.out.print(VerticesTillNowInPath.get(i)+ " ");
                }
                FoundSubpath fpObj = foundPathsList.get(j) ;
                for(int k=0;k<fpObj.vertices.length;k++){
                    System.out.print(fpObj.vertices[k]+" ");
                }
                System.out.println("");
            }
    }

    boolean DfsModified(Integer v,ArrayList<Integer>VerticesTillNowInPath,Integer source,Integer dest){


        if(v.equals(dest)){
          addAllViableSubpathsToMap(VerticesTillNowInPath);
          status[v] = 2;
          return true;
        }

        // If vertex v is already explored till destination, just print all subpaths that meet criteria, using hashmap.
        if(status[v] == 1 || status[v] == 2){
          printViablePaths(v,VerticesTillNowInPath);
          }

        // Vertex in current path. Return to avoid cycle.
        if(status[v]==1){
          return false;
        }

        if(status[v]==2){
              return true;
            }

        status[v] = 1;
        boolean completed = true;

        ArrayList<Integer>toVtcs = adjList.get(v);

        if(toVtcs==null){
            status[v] = 2;
            return true;
        }

        for(int i=0;i<toVtcs.size();i++){

          Integer vDest = toVtcs.get(i);

           VerticesTillNowInPath.add(vDest);

           boolean explorationComplete =  DfsModified(vDest,VerticesTillNowInPath,source,dest);

           if(explorationComplete==false){
           completed = false;
           }

           VerticesTillNowInPath.remove(VerticesTillNowInPath.size()-1);

        }

        if(completed){
            status[v] = 2;
        }else{
            status[v] = 0;
        }

        return completed;

    }


}


public class AllPathsCaller {

    public static void main(String[] args){

        int numOfVertices = 20;
        /* This is the number of attempts made to create an edge. The edge is usually created but may not be ( eg, if an edge already exists between randomly attempted source and destination.*/
        int numOfEdges = 200;
        int src = 1;
        int dest = 10;
        AllPaths allPaths = new AllPaths(numOfVertices);

        allPaths.randomlyGenerateGraph(numOfEdges);
        allPaths.printInputGraph();

        ArrayList<Integer>VerticesTillNowInPath = new ArrayList<Integer>();
        VerticesTillNowInPath.add(new Integer(src));
        System.out.println("List of Paths");
        allPaths.DfsModified(new Integer(src),VerticesTillNowInPath,new Integer(src),new Integer(dest));

        System.out.println("done");




    }



}

I think you are on the right track with BFS. I came up with some rough vaguely java-like pseudo-code for a proposed solution using BFS. The idea is to store subpaths found during previous traversals, and their lengths, for reuse. I'll try to improve the code sometime today when I find the time, but hopefully it gives a clue as to where I am going with this. The complexity, I am guessing, should be order O(E).

,

Further comments:

This seems like a reasonable approach, though I am not sure I understand completely. I've constructed a simple example to make sure I do. Lets consider a simple graph with all edges weighted 1, and adjacency list representation as follows:

A->B,C

B->C

C->D,F

F->D

Say we wanted to find all paths from A to F, not just those in range, and destination vertices from a source vertex are explored in alphabetic order. Then the algorithm would work as follows:

First starting with B: ABCDF ABCF

Then starting with C: ACDF ACF

Is that correct?

A simple improvement in that case, would be to store for each vertex visited, the paths found after the first visit to that node. For example, in this example, once you visit C from B, you find that there are two paths to F from C: CF and CDF. You can save this information, and in the next iteration once you reach C, you can just append CF and CDF to the path you have found, and won't need to explore further.

To find edges in range, you can use the conditions you already described for paths generated as above.

A further thought: maybe you do not need to run Dijkstra's to find shortest paths at all. A subpath's length will be found the first time you traverse the subpath. So, in this example, the length of CDF and CF the first time you visit C via B. This information can be used for pruning the next time C is visited directly via A. This length will be more accurate than that found by Dijkstra's, as it would be the exact value, not the lower bound.

Further comments: The algorithm can probably be improved with some thought. For example, each time the relaxation step is executed in Dijkstra's algorithm (steps 16-19 in the wikipedia description), the rejected older/newer subpath can be remembered using some data structure, if the older path is a plausible candidate (less than upper bound). In the end, it should be possible to reconstruct all the rejected paths, and keep the ones in range.

This algorithm should be O(V^2).

I think visiting each vertex only once may be too optimistic: algorithms such as Djikstra's shortest path have complexity v^2 for finding a single path, the shortest path. Finding all paths (including shortest path) is a harder problem, so should have complexity at least V^2.

My first thought on approaching the problem is a variation of Djikstra's shortest path algorithm. Applying this algorithm once would give you the length of the shortest path. This gives you a lower bound on the path length between the two vertices. Removing an edge at a time from this shortest path, and recalculating the shortest path should give you slightly longer paths.

In turn, edges can be removed from these slightly longer paths to generate more paths, and so on. You can stop once you have a sufficient number of paths, or if the paths you generate are over your upper bound.

This is my first guess. I am a newbie to stackoverflow: any feedback is welcome.