Finding best path trought strongly connected component

Question

I have a directed graph which is strongly connected and every node have some price(plus or negative). I would like to find best (highest score) path from node A to node B. My solution is some kind of brutal force so it takes ages to find that path. Is any algorithm for this or any idea how can I do it?

Answer 1

Have you tried the A* algorithm?

It's a fairly popular pathfinding algorithm. The algorithm itself is not to difficult to implement, but there are plenty of implementations available online.

Dijkstra's algorithm is a special case for the A* (in which the heuristic function h(x) = 0).

There are other algorithms who can outperform it, but they usually require graph pre-processing. If the problem is not to complex and you're looking for a quick solution, give it a try.

EDIT:

For graphs containing negative edges, there's the Bellman–Ford algorithm. Detecting the negative cycles comes at the cost of performance, though (worse than the A*). But it still may be better than what you're currently using.

EDIT 2:

User @templatetypedef is right when he says the Bellman-Ford algorithm may not work in here.

The B-F works with graphs where there are edges with negative weight. However, the algorithm stops upon finding a negative cycle. I believe that is a useful behavior. Optimizing the shortest path in a graph that contains a cycle of negative weights will be like going down a Penrose staircase.

What should happen if there's the possibility of reaching a path with "minus infinity cost" depends on the problem.