Does Dijkstra algorithm always find shortest distance when it reaches any node for the first time?

Yes, Dijkstra’s algorithm always finds the shortest distance to a node when it reaches that node for the first time during its execution. This is a fundamental property of Dijkstra’s algorithm, which ensures that once a node is reached and marked as “visited,” the shortest path to that node from the source has been found.

Dijkstra’s algorithm explores the nodes of a graph in a greedy manner, always selecting the node with the minimum distance (shortest distance) from the source that has not been visited yet. As the algorithm progresses, it maintains the shortest distance to each node in a data structure (commonly a priority queue or min-heap).

When the algorithm selects a node and marks it as visited, it means that the shortest path to that node from the source has been determined. The algorithm will not revisit that node again, as it does not need to explore it further to find a shorter path. This property ensures that Dijkstra’s algorithm correctly computes the shortest paths in a graph from the source to all other reachable nodes.

However, it’s essential to note that Dijkstra’s algorithm assumes that the graph does not contain negative edge weights. If there are negative edge weights, the algorithm may not produce the correct shortest paths. In such cases, you would need to use algorithms like the Bellman-Ford algorithm, which can handle graphs with negative edge weights (though with a higher time complexity than Dijkstra’s algorithm)