Using depth first search to find the number of unique routes to a node

Question

I have a directed graph with vertexes ABCDE. Using a depth first search, if I wanted to be able to find the number of unique routes from A-C (for example), how would I go about doing it? Here is my current DFS.

private final Map<Character, Node> mNodes;
private final List<Edge> mEdges;
private List<Node> mVisited = new ArrayList<>();
int weight;
int numberOfPaths;

public DepthFirstSearch(Graph graph){
    mNodes = graph.getNodes();
    mEdges = new ArrayList<>(graph.getEdges());
    for(Node node : mNodes.values()){
        node.setVisited(false);
    }
}

public void depthFirstSearch(Node source){

    source.setVisited(true);
    List<Edge> neighbours = source.getNeighbouringEdges(mEdges);
    for(Edge edge : neighbours){
        System.out.println(edge.getFrom().getName()+"-"+edge.getTo().getName());
        if(!edge.getTo().isVisited()){

            mVisited.add(edge.getTo());
            weight += edge.getWeight();
            depthFirstSearch(edge.getTo());

        }
    }

If the graph contains cycles the number of path could be infinite. Maybe your graph happens to be acyclic? — snakile, May 30 '16 at 20:00

snakile · Answer 1 · 2016-05-30T20:55:10.743

Assuming the graph is a DAG (i.e., there are no cycles in the graph), you can use dynamic programming and solve your problem in linear time.

The following trivial claim characterizes the number of paths from u to v in the graph:

If u=v then the number of paths from u to v is 1. Otherwise, the number of paths from u to v is the total number of paths from w to v such that (u,w) is an edge in the graph.

The claim implies a simple recursive algorithm, given by the following pseudo code. Note that the pseudo code bellow doesn't use dynamic programming, but a naive recursion. If you need to solve the problem in linear time you should use memoization.

def count_paths(u,v):
    if u == v: return 1
    count = 0
    for each edge (u,w):
        count += count_paths(w,v)
    return count

And here's the code in Java:

public int countPaths(Graph graph, Node u, Node v) {
    nodes = graph.getNodes();
    edges = new ArrayList<>(graph.getEdges());
    if (u.equals(v)) return 1;
    int count = 0;
    List<Edge> neighbours = u.getNeighbouringEdges(edges);
    for(Edge edge : neighbours){
        w = edge.getTo();
        count += countPaths(graph, w, v);
    }
    return count;
}

This method doesn't appear to show unique paths. I get the same path twice. — spogebob92, May 30 '16 at 20:47
@spogebob92, can you provide a simple example in which the algorithm over counts? — snakile, May 30 '16 at 21:36

Using depth first search to find the number of unique routes to a node

1 Answers1