Dijkstra's Algorithm for Shortest Paths

Dijkstra’s Algorithm (shortest path on a weighted graph) Purpose: Find the cheapest/shortest

path from a start vertex to another vertex. How it works (simple): Pick a starting

vertex. Give it a distance of 0. Everything else starts at ∞.

Choose the smallest distance that hasn’t been “locked in” yet. Update its neighbors

using: new distance = current distance + edge weight Lock it in and move

on. Keep repeating until you reach the target vertex. Key idea:

You slowly build the shortest path map using the smallest distances first.