Algorithm for finding distinct paths from A to B in weighted, directed, cyclic graph
-
29-10-2019 - |
Question
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.
Solution
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
.
OTHER TIPS
Simple recursion. You have it in exponential time. Obviously, no zero-weight cycles allowed.
function noe(node N, limit weight W)
no. of path is zero if all outgoing edges have weight > W
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.
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.