Dijkstra Algorithm Questions Medium
In the Dijkstra Algorithm, the role of a path addition is to update the shortest path from the source vertex to all other vertices in the graph.
Initially, all vertices are assigned a tentative distance value, which is set to infinity except for the source vertex, which is set to 0. The algorithm then selects the vertex with the smallest tentative distance and considers it as the current vertex.
For each neighboring vertex of the current vertex, the algorithm calculates the distance from the source vertex through the current vertex. If this distance is smaller than the previously assigned tentative distance for the neighboring vertex, the tentative distance is updated to the new smaller value.
The path addition step comes into play when updating the tentative distances. When a shorter path to a neighboring vertex is found, the algorithm adds this path to the current vertex, effectively extending the shortest path. This path addition ensures that the algorithm keeps track of the shortest path from the source vertex to each vertex as it progresses.
By continuously adding paths and updating tentative distances, the Dijkstra Algorithm gradually builds the shortest path tree, until all vertices have been visited and the shortest path from the source vertex to each vertex has been determined.