Dijkstra’s algorithm is based on

Answer: Greedy approach

Key idea: Repeatedly select the unvisited vertex with the smallest tentative distance, finalize that distance, and relax its outgoing edges to update neighbors' tentative distances.

• Initialize: set the source vertex distance to 0 and all other vertices to infinity; mark all vertices as unvisited.

• Repeat: choose the unvisited vertex with the smallest tentative distance, mark it as visited (finalize its shortest distance), and for each outgoing edge from that vertex, perform relaxation to update neighboring tentative distances if a shorter path is found.

• Stop when all vertices are visited or when the target vertex has been finalized (if searching for a single-source to single-target shortest path).

Time complexity: Using a binary heap (priority queue) gives O((V + E) log V). Using a simple array gives O(V^2).

Why it works: When the algorithm selects the unvisited vertex with the smallest tentative distance, there cannot exist a shorter path to that vertex through any other unvisited vertex, because any path through another unvisited vertex would have to pass through a vertex with distance at least as large and therefore would be no shorter. This guarantees that the chosen tentative distance is final.