Find all paths of exact length and cost in graph

Question 1

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)

Question 2

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.

Question 3

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.

Question 4

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:

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).