Graph theory: possible paths costs values between two vertices

Question

G is an oriented weighted graph. Branch weights are called costs. A path is a sequence of edges which connects a sequence of vertices. A path length is the number of edges involved in this path. The cost of a path is the sum of the edges costs involved in this path. How can we compute all the possible costs values for all different paths of length n connecting chosen two vertices?

Answer 1

For small $n$, you could get away by exponentiating the cost matrix in a similar way to exponentiating the adjacency matrix of a simple graph to count the number of walks. You could quickly get into trouble though, when you have two paths to a node. So I'd say the way to get all the possible costs is to actually traverse the graph and calculate them. You may find the K-Shortest Path problem to be relevant here. The Wikipedia page has a good introduction to the problem, as well as some algorithms listed.

http://en.wikipedia.org/wiki/K_shortest_path_routing

Best of luck!