Weighted Graph Algorithm

2
votes

I have a weighted, directed graph with multiples edges starting from the ending at 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?

4
algorithmgraph
Your question seems quite strange, given that if you want to find all the paths and their costs, you can just enumerate them and sum the edges costs to get the total cost. Maybe you want the shortest path? – wendazhou
It sounds like a flow network problem, such as computing the maximum flow of oil through a set of directed but highly interconnected pipes. Google "Ford-Fulkerson method" or "flow network algorithms" is likely bring up relevant hits. – Morten Mertner

4 Answers

2
votes

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.

0
votes

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.

0
votes

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)

0
votes

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.