3

I have a DAG that has the following adjacency list

L | G, B, P
G | P, I
B | I
P | I
I | R
R | \

I want to find all paths from L to R. I know that I have to do some kind of DFS, and this is what I have so far. (Excuse the Javascript)

function dfs(G, start_vertex) {

    const fringe = []
    const visited = new Set()
    const output = []
    fringe.push(start_vertex)

    while (fringe.length != 0) {
        const vertex = fringe.pop()
        if (!visited.has(vertex)) {
            output.push(vertex)
            for (neighbor in G[vertex].neighbors) {
                fringe.push(neighbor)
            }
            visited.add(vertex)
        }
    }

    return output
}

The output of dfs(G, "L") is [ 'L', 'P', 'I', 'R', 'B', 'G' ] which is indeed a depth first traversal of this graph, but not the result I'm looking for. After doing some searching, I realize there may be a recursive solution, but there were some comments about this problem being "NP-hard" and something about "exponential paths" which I don't understand.

Carpetfizz
  • 8,707
  • 22
  • 85
  • 146
  • 1
    The problem in general case isn't even NP (a solution can't be checked in polynomial type since it has non-polynomial size), but this shouldn't concern you. – Abstraction Mar 28 '17 at 14:32
  • @Abstraction good, because I can eyeball a solution in 10 seconds :) – Carpetfizz Mar 28 '17 at 14:33

2 Answers2

2

The problem is indeed np-hard because the number of possible paths between two nodes is exponential to the number of nodes. so no way around having a worst-case exponential runtime.

Amnon
  • 195
  • 3
  • 12
  • Just because the first solution that comes to mind is exponential it doesn't mean the problem is exponential. A lot of DP problems are exponential too if implemented in a naive way. – Wildhammer Oct 12 '21 at 15:56
  • Well, I don't mention a specific solution here. I just say that in the worst case scenario (runtime-wise) there might be an exponential number of paths (exponential to the number of nodes) so even if you find a solution in which finding a path in O(1) time, you have exponential number of such paths, which means you need an exponential runtime to find all of them. I think it's quite clear that finding more than one path in O(1) is impossible since you have to at least return a pointer to that path, which is O(1) per path already – Amnon Oct 28 '21 at 13:00
1

All paths with start head to vertex vertex can be split into paths with heads head||v where v is adjacent to final vertex of head, unless final vertex of head is already vertex: (pseudo-javascript, can have syntax problems)

function print_all_rec(G, head, vertex){
  if(head[head.length-1] == vertex){
    print(head); //we're here
    return;
  }
  for(v in head[head.length-1].neighbors){
    var newHead = head; newHead.append(v);
    print_all_rec(G, newHead, vertex);
  }
}

function print_all_routes(G, from, to){
  var start = [];
  start.append(from);
  print_all_rec(G, start, to);
}
Abstraction
  • 1,108
  • 11
  • 25