When two or more unvisited nodes have the same tentative distance, the algorithm allows for any of them to be chosen next. This situation typically arises when the graph contains multiple paths of equal total weight leading to different nodes. Dijkstra’s algorithm does not specify a unique tie-breaking rule, so the choice between equal-distance nodes may depend on how the algorithm is implemented (e.g. alphabetical order, order of insertion into a priority queue, etc.). Importantly, choosing any of these equally distanced nodes does not affect the correctness of the final distances or the algorithm’s guarantee to find the shortest paths, because all visited nodes are updated based on minimum distances at each step. However, if there are multiple shortest paths to a node with the same total weight, the specific previous node recorded might vary depending on which path is taken first. This means the reconstructed path may differ, but it will always be correct in terms of overall distance.

Yes, Dijkstra’s algorithm can handle graphs that include unreachable nodes, and this should be reflected clearly when tracing. If a node cannot be reached from the starting node — meaning there is no path connecting it either directly or indirectly — its tentative distance will remain at infinity throughout the trace. It will also never be visited, because the algorithm always chooses the unvisited node with the lowest tentative distance, and infinity is never the lowest value. This makes it easy to identify unreachable nodes during a trace, and they should be clearly marked as such in your distance table. If you're asked to trace the algorithm and provide final distances, be sure to include unreachable nodes and note that their distances are still infinity and that no path exists to reach them. These cases often appear in exam questions to test whether students understand how Dijkstra’s algorithm deals with disconnected graphs.

Recording the previous node for each visited node is a key part of tracing Dijkstra’s algorithm because it allows the shortest path to be reconstructed once the algorithm has completed. Without this, you would only know the minimum distance to each node, but not how to actually travel from the start node to that destination. During the algorithm, whenever a node’s tentative distance is updated because a shorter path is found, the current node is set as the previous node for that neighbour. This tracking forms a chain of references from each node back to the source. When the trace is finished, you can reconstruct the full shortest path to any node by following the chain of previous nodes in reverse. For example, to find the shortest path from A to E, you might go from E to D to B to A if those were the previous nodes, and then reverse the path to get the correct order.

In a directed graph, you stop tracing Dijkstra’s algorithm using the same rule as in an undirected graph: once all nodes have been visited, or if you are tracing to a specific target node, once the target has been marked as visited. The direction of the edges matters only in that some connections may be one-way — this affects which neighbours are considered when visiting a node. For instance, if there is an edge from A to B but not from B to A, then when visiting B, A will not be treated as a neighbour. During tracing, you must only consider outgoing edges from the current node when checking for neighbours. Directed graphs are particularly useful in modelling real-world problems like road networks with one-way streets or dependency chains in scheduling. If a node is unreachable due to edge direction, it will remain at infinity and unvisited, just as in undirected graphs with disconnected components.

The fundamental logic of tracing Dijkstra’s algorithm remains the same regardless of whether a priority queue or a basic list is used to select the next node. However, the efficiency and clarity of the tracing process can change. In a priority queue implementation, nodes are automatically ordered based on their current tentative distances, so retrieving the node with the smallest distance is very efficient — this makes tracing smoother and reduces errors in node selection. In contrast, when using a basic list, you must manually scan the entire list of unvisited nodes at each step to find the one with the smallest tentative distance. This manual process can be more error-prone during a trace, especially in graphs with many nodes. For exam tracing, students typically use a list-based approach and pick the lowest-distance node by inspection. While this works for small graphs, understanding the role of priority queues helps explain why the algorithm performs better on large-scale data.