Algorithm for finding distinct paths from A to B in weighted, directed, cyclic graph

9
votes

Suppose we have a DIRECTED, WEIGHTED and CYCLIC graph.

Suppose we are only interested in paths with a total weight of less than MAX_WEIGHT

What is the most appropriate (or any) algorithm to find the number of distinct paths between two nodes A and B that have a total weight of less than MAX_WEIGHT?

P.S: It's not my homework. Just personal, non-commercial project.

3
algorithmgraphgraph-algorithmpath-finding
Do you allow paths that visit the same vertex more than once (provided the length of the path is less than MAX_WEIGHT)? - NPE
Can we assume no zero-weight cycles? - user684934
@aix: Yes, sorry forgot to mention. You can loop around as much as you want as long as MAX_WEIGHT criteria is met. - Babak
@bdares: I'm not entirely sure what zero-weight cycle means. You can assume every edge has a weight greater than 0. - Babak
What's the meaning of distinct paths? - Saeed Amiri

3 Answers

2
votes

If the number of nodes and MAX_WEIGHT aren't too large (and all weights are integers), you can use dynamic programming

unsigned long long int num_of_paths[MAX_WEIGHT+1][num_nodes];

initialize to 0, except num_of_paths[0][start] = 1;.

for(w = 0; w < MAX_WEIGHT; ++w){
    for(n = 0; n < num_nodes; ++n){
        if (num_of_paths[w][n] > 0){
            /* for each child c of node n
             * if w + weight(n->c) <= MAX_WEIGHT
             * num_of_paths[w+weight(n->c)][c] += num_of_paths[w][n];
             */
        }
    }
}

solution is sum of num_of_paths[w][target], 0 <= w <= MAX_WEIGHT .

1
votes

Simple recursion. You have it in exponential time. Obviously, no zero-weight cycles allowed.

function noe(node N, limit weight W)

  1. no. of path is zero if all outgoing edges have weight > W

  2. otherwise no. of path is sum of numbers of path obtained by sum(noe(C1,W-W1),noe(C2,W-W2),... noe(Cn,W-Wn)) where C1 ... Cn are the nodes connected to N for which W-Wi is not negative where Wi is weight of the connecting edge, written in your favorite language.

More eficient solution should exist, along the lines of Dijkstra's algorithm, but I think this is enough for homework.

0
votes

Your problem is more general case of K-Disjoint Path In directed planar graphs, with not fixed K.

K disjoint paths problem for directed planar graphs is as this:

given: a directed planar graph G = (V;E) and k pairs (r1; s1); .... ; (rk; sk) of vertices of G;

find: k pairwise vertex-disjoint directed paths P1; ... ; Pk in G, where Pi runs from ri to si (i = 1; .... ; k).

In k-disjoint path you can draw arc from all si to B, and Also arc from A to all ri by this way you create graph G' from G.

Now if you can solve your problem in G' in P you can solve k-disjoint Path in G, So P=NP.

But if you read the paper linked it gives some idea for general graph (solving k-disjoint path with fixed k) and you can use it to have some good approximation.

Also there is more complicated algorithm which solves this problem in P (for fixed k) in general graphs. but in all it's not easy (it's by Seymour ).

So your best choice currently is to use brute force algorithms.

Edit: Because MAXWEIGHT is independent to your input size (your graph size) It doesn't affect to this problem, Also because it's NP-Hard for undirected unweighted graph, still you simply can conclude it's NP-Hard.