gen-define-dijkstra-s-algorithm-and-give-one-short-worked-exampl-4ac8

Define Dijkstra's algorithm and give one short worked example.

# Dijkstra's Algorithm **Definition:** Dijkstra's algorithm finds the shortest path from a starting node to all other nodes in a weighted graph with non-negative edge weights. It works by repeatedly selecting the unvisited node with the smallest known distance and updating its neighbors. ## Short Worked Example Find the shortest path from A to all other nodes: ``` Graph: A ---2--- B | | 1 3 | | C ---1--- D ``` **Steps:** | Step | Current | Distances [A, B, C, D] | Visited | |------|---------|------------------------|---------| | 0 | - | [0, ∞, ∞, ∞] | {} | | 1 | A | [0, 2, 1, ∞] | {A} | | 2 | C | [0, 2, 1, 2] | {A, C} | | 3 | B | [0, 2, 1, 2] | {A, C, B} | | 4 | D | [0, 2, 1, 2] | {A, C, B, D} | **Result:** - A→A: 0 - A→B: 2 (via A→B) - A→C: 1 (via A→C) - A→D: 2 (via A→C→D) The algorithm maintains a priority queue of unvisited nodes, always processing the one with minimum distance, guaranteeing optimal paths.