2

I'm currently in the middle of an optimization problem. I'm using dynamic programming and after I'm done with computations, I'm left with N x N matrix that says: if you take mat[i][j] then the value is cost of traveling from i to j == an adjacency matrix.

I also have access to two variables, K and C, which could be interpreted as length of path and cost of path, respectively.

So is there an algorithm, that can find all paths that have length K and cost C?

EDIT:

Here is an sample of adjacency matrix. The path is from 0 -> 8, cost is 48 and length is 3.

So for example, one valid path would be: 0->3 (15), 3->6 (15 + 13), 6->8 (15 + 13 + 20 = 48). Another might be : 0->4 (20), 4->6 (20 + 8), 6 -> 8 (20 + 8 + 20 = 48).

Non-valid path might include: 0->1(8), 1->2(8 + 4), 2->3(8 + 4 + 3), 3->4 (8 + 4 + 3 +5), ..., but length greater than 3, so that is invalid, same thing 0->8 has cost 48, but length 1.

    1   2   3   4   5   6   7   8
---------------------------------
0:  8  12  15  20  26  28  37  48
1:----  4   7  12  18  20  29  40
2:--------  3   8  14  16  25  36
3:------------  5  11  13  22  33
4:----------------  6   8  17  28
5:--------------------  2  11  22
6:------------------------  9  20
7:---------------------------- 11

Actually, looking at it now, I see I have to rephrase my question. The number of vertices is determined during input from user, so is the length and cost. You always travel from first to last vertex. No matter what path you take (ignoring length now), getting from first to last vertex always has cost C, only thing that varies is length.

So the new (and better) question is, how to find all paths from first vertex to last, with length K?

isklenar
  • 974
  • 2
  • 14
  • 34
  • 2
    This problem is easily reduceable from the [longest path problem](http://en.wikipedia.org/wiki/Longest_path_problem) which is [NP Complete](http://en.wikipedia.org/wiki/NP-complete), which means your problem is NP Complete as well. An exponential solution could be DFS - just check all paths of length K. – amit Dec 15 '13 at 19:10
  • Are there any constraints on the degrees of the vertices or the weights of the edges? What's the optimization problem? As amit says, this is NP-complete, but with information about the context we might be able to find a way to cheat. If we can't cheat: how many nodes are in the graph? Are you looking for an efficient algorithm, or just a correct one? – Andy Jones Dec 18 '13 at 00:06
  • 1
    The number of paths of exact length K = C(n,K) * (K!) = n*(n-1)*(n-2)*...(n-K+1). Hence the number of possible paths is of the order of O(n!). This is an even faster rate of growth than exponential complexity. In the worst case you may have to enumerate all these paths if the costs of all the edges (and hence paths) are equal. As pointed out, you can do this using recursion, but only for small n. For a large value of n, it will take a lot of time and may even consume all your stack memory. – Abhishek Bansal Dec 18 '13 at 09:02
  • @AndyJones I added some info and rephrased my question. It should be clearer and the question now only ask for paths of length K, since the cost will always be equal. – isklenar Dec 18 '13 at 12:11
  • Are all the verticles adjacent? – h8red Dec 21 '13 at 11:33
  • Do the costs always increase as you go to a higher numbered vertex (in your example, the costs for vertex 0 are 8 12 15 20 26 28 37 48, do they always increase this way?) This could vastly simplify things... Also, can you go from vertex 5 to 0 (are the paths bidirectional?). Can the paths have repeated nodes? repeated edges maybe? – maniek Dec 21 '13 at 15:55

4 Answers4

2

OP says: You always travel from first to last vertex. So:

  • for any i->j, the index j must be greater than i.

And as the example (and according to the OP's explaination), the cost of edges is linear additive. It mean that:

  • mat[i][k] + mat[k][j] = mat[i][j]

So:

  • C(i->j) == C if and only if mat[i][j] == C.

Assuming there exists mat[i][j] == C and j-i<=K, the problem could be simplified to select K-1 nodes from i+1 to j-1, and list all the combinations. You could simply do this by Algorithm to return all combinations of k elements from n.

Here I wrote a code to solve your example in python for test:

N = 9
mat = [None] * (N-1)
mat [0] =[None,    8,   12,   15,   20,   26,   28,   37,   48]
mat [1] =[None, None,    4,    7,   12,   18,   20,   29,   40]
mat [2] =[None, None, None,    3,    8,   14,   16,   25,   36]
mat [3] =[None, None, None, None,    5,   11,   13,   22,   33]
mat [4] =[None, None, None, None, None,    6,    8,   17,   28]
mat [5] =[None, None, None, None, None, None,    2,   11,   22]
mat [6] =[None, None, None, None, None, None, None,    9,   20]
mat [7] =[None, None, None, None, None, None, None, None,   11]

def xcombination(seq,length):
    if not length:
        yield []
    else
        for i in xrange(len(seq)):
            for result in xcombination(seq[i+1:],length-1):
                yield [seq[i]]+result

def find_path(C, K):
    i_j = []
    paths = []
    for i in range(N):
        for j in range(i+1, N):
            if mat[i][j] == C:
                i_j.append([i, j])
    for p in i_j:
        if p[1]-p[0] >= K:
            paths += [[p[0]]+i+[p[1]] for i in xcombination(range(p[0]+1, p[1]), K-1)]
    return paths


paths = find_path(48, 3)
for path in paths:
    for step in range(len(path)-1):
        print str(path[step])+"->"+str(path[step+1])+"("+str(mat[path[step]][path[step+1]])+") ", 
    print

The output answer to your example:

0->1(8)      1->2(4)      2->8(36)
0->1(8)      1->3(7)      3->8(33)
0->1(8)      1->4(12)      4->8(28)
0->1(8)      1->5(18)      5->8(22)
0->1(8)      1->6(20)      6->8(20)
0->1(8)      1->7(29)      7->8(11)
0->2(12)      2->3(3)      3->8(33)
0->2(12)      2->4(8)      4->8(28)
0->2(12)      2->5(14)      5->8(22)
0->2(12)      2->6(16)      6->8(20)
0->2(12)      2->7(25)      7->8(11)
0->3(15)      3->4(5)      4->8(28)
0->3(15)      3->5(11)      5->8(22)
0->3(15)      3->6(13)      6->8(20)
0->3(15)      3->7(22)      7->8(11)
0->4(20)      4->5(6)      5->8(22)
0->4(20)      4->6(8)      6->8(20)
0->4(20)      4->7(17)      7->8(11)
0->5(26)      5->6(2)      6->8(20)
0->5(26)      5->7(11)      7->8(11)
0->6(28)      6->7(9)      7->8(11)
Community
  • 1
  • 1
Timothy
  • 4,467
  • 5
  • 28
  • 51
0

I don't think it's related to the longest path problem, but I believe computing all path costs of length K can be done in at least pseudo-polynomial time. I don't have an actual implementation yet, just the idea shown below, which looks like it's around O(N^3 * K * P), where P is the number of paths of length <= K (this is just a first-look upper bound, not sure if a tighter limit can be determined).

A somehow related problem that crosses my mind is the following:

"Given the adjacency matrix A of a graph (A[i,j]==1 iff. the edge i->j exists), compute how many paths of length K are between each pair of nodes."

In this case, the answer would be to raise the matrix A to the Kth power, a formula which can be deduced from the following relation:

num_paths[i->j, K] = sum (num_paths[i->x, K-1] * A[x,j]) for all x=1..N

Of course, num_paths[i->j, 1] = A[i,j], and the above formula is in fact the same as the naive matrix multiplication algorithm.

Now, since you have an algorithm to compute the number of paths of a given length between all pairs of nodes, switching to computing all their costs is a matter of replacing 'sum' above with 'union' and instead of "num_paths[i->x, K-1] * A[x,j]", do something along the lines of 'add cost[x,j] to each path of length K-1 between i->x".

Let me know if you need further clarifications.

Catalin Pol
  • 261
  • 1
  • 3
  • It's certainly related to the longest path problem because if you could solve the OP's problem efficiently, you could perform a binary search to efficiently identify whether the longest path in an undirected, unweighted graph is of size at least `k`, solving an `NP`-complete problem. With the matrix powering: that counts *walks*, not paths. Walks do not have to be edge-disjoint. – Andy Jones Dec 19 '13 at 16:09
0

You could try to write your own algo without using other packages. So first find all node connect to your start node, say 1. you may have[1,2],[1,4],[1,7], and then find all node connect to 2, 4, and 7. then you may have [1,2,3],[1,4,5],[1,7,6], repeat the process untill Kth iteration. select all paths end with you target node. if you dont want cycle, which means each node can be visited oncc. you can add a sign to each node with True(have visited) or False(havent visited yet).
Note: this is the most straight forward way, also a "dummy" way. If N is not too large and 1 < K < < N, it works well otherwise it may cost a lot of time and memory.

What's more I dont agree with Cata, get the number of paths and get all paths are different things.

Luyi Tian
  • 371
  • 1
  • 12
0

If all verticles are adjacent, u simply get the binominal coefficient as an answer: there are

(n-1)!/((k-1)!(n-k)!)

paths. It can be easily shown: out path of length k is (0 v1 v2 .. v(k-1) n). So we have to choose (k-1) disctinct values from 1, 2,.., n-1. Thus, we need to calculate the number of (k-1)-combinations.

If not, we can use a dp idea to caculate the number of paths. Let f(i,j) be the amount of the paths from s to i with length j. Then f(i,j)= sum f(w, j-1) * F[w,i], where F[w,i] = 1 if theres a way from w to i, and 0 otherwise. This can be done in a following way: crate a matrix F[i,j] (should be (n+1)*(n+1)) and calculate F^k (exponentiation by squaring can be used here, leading to a O(n^3 * log k) solution). The answer should be F^k(0,n) But this idea works only if the graph doesnt have cycles.

If there are cycles, the best idea i can think of (probable there are better ones) is this. Let f(i, m) be the anount of paths from s (starting verticle) to i, visiting only verticles from m (m is a set). Let g(i, m) be the amount of paths from i to t (the last one), visiting obly verticles from m. We count f(i, m) for all the path with length k/2, and g(i,m) - with length k-k/2. Then we have to iterate through the middle verticle v of the path from s to t and find such sets m1 (from f) and m2 (from g) that have only v in common, and calculate the sum of f(v, m1) * g(v, m2). So we can search the correct pairs of (m1, m2) by iterating through all the m1s.

If we have to output the path, not calculate the amount, then:

  1. If all the verticles are adjacent, we can generate all the (k-1)-combinations of (1, 2, ..., n-1), which is a classical combinatorics algorithm.

2 If not, i can think only of dfs, which can become exponential (as the number of path can be exponential).

h8red
  • 713
  • 4
  • 17