Weighted Graph Algorithm

I have a weighted, directed graph with multiples edges starting from the ending a开发者_StackOverflowt the same nodes. Ex. Multiple edges going from node A to node B.

What would be the best search algorithm to get all of the paths to a certain node and the associated costs of these paths?

---

Since you want all the paths, I'd use a simple breadth-first search. However, I also suggest that you collapse all the parallel edges into a single edge that has a list of weights.

Once you get all the different paths (that is, all the paths in which the nodes visited are different), for each path you can calculate all the possible alternative parallel routes.

So if you've got the following edges:

A -> C  (5)
A -> C  (3)
A -> B  (7)
B -> C  (1)
B -> C  (4)

The first step transforms it into:

A -> C (5,3)
A -> B (7)
B -> C (1,4)

The breadth-first search on this graph will yield the following paths between A and B:

A -> B (7)
A -> C -> B (5,3) + (1,4)

So for the second path, you'll get the following costs:

5 + 1 
5 + 4
3 + 1
3 + 4

This isn't going to be any faster in itself than just doing a BFS on the original graph, but a simpler graph is easier to handle.

---

If you have to output the cost of each path, there is nothing better than a plain DFS (or BFS). Since the problem is output sensitive and you might just have O(E + V) paths, you cannot accomplish anything better in terms of big-O notation.

---

As already stated, you can do bruteforce/backtracking using Depth First Search, etc.

Don't expect to find any shortcuts for this - if your graph is dense enough there can be lots of paths and even just finding how many of them there are is #P-complete (ie.: untractable).

(If your problem is different - maybe repeated nodes are allowed or you only want to find the shortest path or something like that then there could be tractable solution)

---

do you allow the cycling, that is you have directed link/path from a->b b-x-x-->a? for which case you will end up with unlimited paths.