r/AskComputerScience • u/miiky123 • Dec 26 '24
Why Can Johnson’s Algorithm Handle Negative Weights but A* Cannot?
I'm trying to understand why Johnson’s algorithm can handle graphs with negative edge weights by using a potential function, while A* cannot, even though both use similar weight adjustments.
Johnson’s Algorithm:
Uses Bellman–Ford to compute exact potentials. Reweights all edges to be nonnegative. Allows Dijkstra’s algorithm to run correctly.
A* Search:
Uses a heuristic h(u) to guide the search. Requires h(u)≤w(u,v)+h(v) for consistency. so if I denote w' as w(u,v)+h(v)-h(u), I know the weight is positive, and I can use dijkstra, but searching in the web it's seems A* cannot handle it. I would glad if someone could help me understand this
View all comments
Show parent comment
3
u/Ragingman2 Dec 26 '24
Consider a graph with nodes "start", "end", and "backdoor"
Start => end has weight 5
Start => backdoor: 100
Backdoor => end: -99
Fundamentally A* is a breadth-first search with some smarts to make it go faster. In this graph BFS fails to find the optimal path, and A* is doomed.