Review an existing Java class that finds the shortest route from a source city to a destination city using weighted edges.
Determine the intended time and space complexity. With a heap, the expected time complexity is O((V + E) log V).
Locate and correct errors in the edge-relaxation and distance-update logic.
Explain why Dijkstra's algorithm fits this navigation scenario, and compare it with A* and Floyd-Warshall.
Follow-up: explain how the approach changes when edges may have negative weights, including Bellman-Ford and its operating method.
Notes
Treat this as a debugging and code-review exercise rather than a from-scratch rewrite. Retain the existing organization where practical and repair the broken invariant.
Address the common Dijkstra errors: failing to replace a node's best-known distance when a shorter route is discovered, marking nodes visited prematurely, and processing stale entries from the heap without a guard.
In the duplicate-push implementation with a binary heap and adjacency list, the target complexity is O((V + E) log V). Whenever an entry is removed from the heap, skip it if its distance is greater than the node's current best distance.
State that Dijkstra requires non-negative edge weights. Bellman-Ford relaxes every edge V - 1 times, then performs one additional pass to identify negative cycles.
Preparation
Practice writing heap-based Dijkstra from memory, including the stale-entry check. Then intentionally damage the relaxation step so you can explain which invariant the review uncovers.
Create a small counterexample showing Dijkstra's failure in the presence of a negative edge, and trace Bellman-Ford on that same graph.
Be ready to make the following comparison: use Dijkstra for sparse navigation graphs with non-negative weights, A* when an admissible geographic heuristic exists, and Floyd-Warshall for all-pairs shortest paths on small or dense graphs.