Dijkstra's Algorithm

Definitions

1. A graph algorithm that finds the shortest path from a source node to all other nodes in a weighted graph with non-negative edge weights. Uses a priority queue to greedily explore the nearest unvisited node. Time complexity: O((V + E) log V) with a binary heap. The foundation of GPS navigation, network routing (OSPF), and game pathfinding.

   In plain English: An algorithm for finding the shortest path between two points in a network, used by every mapping and navigation app.

   Example: "Google Maps uses a variant of Dijkstra's algorithm — it finds the shortest driving route by exploring roads outward from your location."

Etymology

1956

Edsger Dijkstra conceived the algorithm in 20 minutes at a café in Amsterdam, thinking about shortest routes between cities.

1959

Published in Numerische Mathematik, becoming one of the most cited algorithms in computer science.

Related Terms

• Data Structure
• Operational Transform
• Topological Sort
• Dynamic Programming
• Greedy Algorithm
• Divide and Conquer
• Two Pointers
• Sliding Window