Greedy Algorithms Questions Medium
Dijkstra's algorithm is a greedy algorithm that is used to find the shortest path in a connected weighted graph. It works by maintaining a set of vertices for which the shortest path has already been determined. Initially, the distance to all vertices except the source vertex is set to infinity.
The algorithm starts at the source vertex and iteratively selects the vertex with the minimum distance from the set of vertices whose shortest path has not been determined yet. This vertex is then added to the set of vertices with determined shortest paths.
For each selected vertex, the algorithm updates the distances of its neighboring vertices. It calculates the distance from the source vertex to each neighboring vertex through the selected vertex and compares it with the current distance. If the newly calculated distance is smaller, it updates the distance and sets the selected vertex as the previous vertex for the neighboring vertex.
This process continues until all vertices have been added to the set of vertices with determined shortest paths or until the destination vertex is reached. The shortest path can then be reconstructed by following the previous vertices from the destination vertex back to the source vertex.
By selecting the vertex with the minimum distance at each step, Dijkstra's algorithm guarantees that the shortest path to each vertex is determined in a greedy manner. However, it is important to note that Dijkstra's algorithm only works correctly for graphs with non-negative edge weights. If there are negative edge weights, a different algorithm such as Bellman-Ford should be used.