Dijkstra's Algorithm
Dijkstra's Algorithm is a popular algorithm used to find the shortest path from a source vertex to all other vertices in a weighted graph. It works by exploring the graph and expanding the nearest unvisited node (with the smallest tentative distance) at each step, ensuring that the shortest path to any vertex is found.
Key Concepts:
Graph: The algorithm operates on a graph where each edge has a non-negative weight.
Shortest Path Tree (SPT): Dijkstra's algorithm constructs this tree incrementally from the source vertex.
Priority Queue: Often implemented with a min-heap, it helps to efficiently pick the vertex with the smallest tentative distance.