Dijkstra’s algorithm assumes that once a node has been visited and its shortest distance finalised, there is no shorter path to that node. This assumption only holds when all edge weights are non-negative. If a graph contains a negative edge, Dijkstra’s method may prematurely finalise a node’s shortest distance without considering the possibility of a shorter path appearing later through that negative edge. For example, a node might initially be given a tentative distance of 10 and marked as visited, but a different path with a negative edge could later reduce this to 6. Since visited nodes are never revisited in Dijkstra’s algorithm, the shorter path is ignored, resulting in incorrect outputs. This failure to re-evaluate finalised nodes makes the algorithm unsuitable for graphs with negative edge weights. Algorithms like Bellman-Ford are designed to handle such cases because they repeatedly evaluate all edges, allowing shorter paths to be found even after initial updates.

To reconstruct the actual shortest path from the starting node to any other node, Dijkstra’s algorithm must track predecessors during the process. When the algorithm updates a tentative distance for a neighbouring node, it records the current node as the predecessor of that neighbour. This means every node stores a pointer to the node it was reached from on the shortest known path. After the algorithm completes, to determine the full shortest path to a target node, you simply backtrack from that node using the predecessor pointers, forming the path in reverse. For example, if node D was reached from node C, which was reached from node B, and so on until the start node A, then the full path is A → B → C → D. This backtracking is essential in applications like GPS navigation, where knowing the total distance isn’t enough—you need the full route. Without predecessor tracking, only distances are available, not the actual paths.

Yes, while Dijkstra’s algorithm is typically used to find the shortest paths from the source node to all other nodes, it can be easily adapted to stop once the shortest path to a specific target node is found. During its operation, the algorithm always expands the node with the smallest tentative distance. If the target node is selected as the current node during this process, and its tentative distance becomes permanent, the algorithm can immediately terminate. At this point, the shortest path and distance to that target node are guaranteed to be correct. This optimisation is useful in situations where only one destination matters, as it avoids unnecessary processing of unrelated parts of the graph. However, it’s important that the graph still adheres to the required condition of non-negative weights, and that predecessor pointers are stored if the actual route to the target node is needed for output or analysis.

The performance of Dijkstra’s algorithm is significantly influenced by the data structures used, particularly for storing the graph and managing unvisited nodes. If the graph is stored as an adjacency matrix, the algorithm must scan every node to find neighbours, leading to O(V²) time complexity, where V is the number of nodes. This is inefficient for large or sparse graphs. Using an adjacency list improves efficiency by allowing the algorithm to directly access only the relevant neighbours of a node. For managing unvisited nodes, using a simple list or array requires a full scan to find the node with the smallest tentative distance, also leading to O(V²) complexity. Replacing this with a priority queue (typically implemented with a binary min-heap) reduces the time needed to find the next node to O(log V). Combining an adjacency list with a priority queue brings the total complexity down to O((V + E) log V), which is much more scalable for large graphs.

If multiple paths yield the same shortest distance to a node, Dijkstra’s algorithm will still function correctly but will only record one of those paths—typically the first one encountered during the update process. The algorithm updates a node’s tentative distance only when a strictly smaller value is found. If an alternative path results in a distance equal to the existing tentative distance, the algorithm does not update the value or predecessor pointer. As a result, the final output will include one valid shortest path, but not necessarily all possible shortest paths. This behaviour is deterministic and depends on the order in which neighbours are evaluated. If it’s important to find all shortest paths of equal distance, a modified algorithm is required that stores multiple predecessor nodes or explores equal-distance paths further. In standard use, however, returning any one correct shortest path is acceptable and does not affect the correctness of the overall solution.