Weighted Graph Algorithm -

i have weighted, directed graph multiples edges starting ending @ same nodes. ex. multiple edges going node node b.

what best search algorithm of paths node , associated costs of these paths?

since want paths, i'd use simple breadth-first search. however, suggest collapse parallel edges single edge has list of weights.

once different paths (that is, paths in nodes visited different), each path can calculate possible alternative parallel routes.

so if you've got following edges:

a -> c  (5) -> c  (3) -> b  (7) b -> c  (1) b -> c  (4) 

the first step transforms into:

a -> c (5,3) -> b (7) b -> c (1,4) 

the breadth-first search on graph yield following paths between , b:

a -> b (7) -> c -> b (5,3) + (1,4) 

so second path, you'll following costs:

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

this isn't going faster in doing bfs on original graph, simpler graph easier handle.