Debug Dijkstra Shortest Path for Navigation

Intern infotainment technical round: review a Java shortest-path finder for a navigation system, identify bugs in its Dijkstra implementation, analyze complexity, and discuss alternatives for negative weights. Requirements Given an existing Java class that implements a shortest-path finder from a source city to a destination city over weighted edges. Analyze the intended time and space complexity; expected complexity is O((V + E) log V) with a heap. Identify and fix mistakes in the edge-update / relaxation logic. Explain why Dijkstra's algorithm is appropriate for this navigation use case compared with A* and Floyd-Warshall. Follow-up: handle negative edge weights; discuss Bellman-Ford and how it works. Notes This is a debugging / code-review round, not a rewrite-from-scratch round. Preserve the structure where possible and patch the broken invariant. The most common Dijkstra bugs are failing to update a node when a shorter path is found, using a visited set too early, and not skipping stale heap entries. With a binary heap and adjacency list, the target complexity is O((V + E) log V) in the common push-duplicates implementation. When popping, skip entries whose distance is larger than the current best distance. For the negative-edge follow-up, call out that Dijkstra assumes non-negative weights. Bellman-Ford relaxes all edges V - 1 times and can detect negative cycles with one extra pass. Preparation Code heap-based Dijkstra from memory and include the stale-entry guard; then deliberately break relaxation to practice identifying the invariant failure in review form. Prepare a tiny counterexample where Dijkstra fails with a negative edge, and then walk Bellman-Ford over the same graph. Rehearse the comparison: Dijkstra for non-negative sparse navigation graphs, A* when an admissible geographic heuristic is available, Floyd-Warshall only for all-pairs dense or small graphs.