Dijkstra's Algorithm (Shortest Path Algorithm)

This text explains the working principle of Dijkstra's algorithm, which solves the single-source shortest path problem for weighted directed or undirected graphs. Using breadth-first search, the algorithm constructs a shortest path tree and is frequently implemented in routing algorithms or as a component in other graph-based solutions.

Specifically, Dijkstra's algorithm adopts a greedy approach. It maintains a distance array (dis) to store the shortest known distances from the source node to each vertex and a set T to record vertices whose shortest paths have been determined. Initially, the source node s is assigned a path weight of 0 (dis[s] = 0), while all other vertices are set to infinity. The set T initially contains only the source vertex s.

The algorithm then selects the vertex with the minimum value in the dis array (excluding those already in T), which represents the shortest path from s to that vertex. This vertex is added to set T, marking it as processed. Subsequently, the algorithm checks all adjacent vertices of the newly added vertex. If a shorter path is found via this vertex (i.e., dis[current] + edge_weight < dis[neighbor]), the dis array is updated for the neighboring vertices.

This process repeats—selecting the next minimum dis value, adding the vertex to T, and updating neighbors—until T includes all vertices in the graph. Through these iterations, the algorithm guarantees finding the shortest paths from the source to all other vertices.