Dijkstra's Algorithm (Shortest Path Algorithm)
Dijkstra's algorithm employs breadth-first search to solve the single-source shortest path problem for weighted directed or undirected graphs, ultimately producing a shortest path tree. This algorithm is commonly used in routing protocols or as a submodule in other graph algorithms. Dijkstra's algorithm follows a greedy strategy, utilizing a distance array (dis) to store the shortest distances from the source node to all vertices and a set T to track vertices with finalized shortest paths. Initially, the source node s has a path weight of 0 (dis[s] = 0). For vertices directly reachable from s (e.g., vertex m), dis[m] is set to the edge weight w(s, m), while all other vertices are initialized with infinity.