1. Theoretical Foundations: Weighted Graphs and Non-Negative Invariants

Conceived in 1956 and published in 1959 by Dutch computer scientist Edsger Wybe Dijkstra, Dijkstra's Algorithm solves the single-source shortest path (SSSP) problem for weighted graphs. In formal graph theory, a graph is represented as an algebraic tuple G = (V, E), where V denotes a finite set of vertices (or nodes) and E denotes a collection of edges connecting pairs of vertices. Each edge (u, v) ∈ E carries an associated scalar cost or weight w(u, v) representing distance, latency, impedance, or financial cost.

The foundational mathematical prerequisite of Dijkstra's algorithm is the Non-Negative Weight Invariant:

w(u, v) ≥ 0  for all (u, v) ∈ E

Dijkstra's algorithm operates on a fundamental greedy assumption: once a vertex is marked as "visited" (its minimum distance finalized), no subsequent edge relaxation can ever discover a shorter path to that vertex. If a graph contains negative edge weights (such as an edge with weight -5), traversing through that edge could retroactively reduce the path cost to an already-settled node. In such scenarios, Dijkstra's algorithm fails, and alternative algorithms—such as the Bellman-Ford algorithm (which handles arbitrary negative weights in O(V · E) time) or the Floyd-Warshall algorithm (for all-pairs shortest paths in O(V³) time)—must be utilized.

2. The Core Mechanics: Greedy Selection and Edge Relaxation

Dijkstra's algorithm maintains three dynamic data structures throughout execution:

• Tentative Distance Vector (dist[]): Stores the currently known shortest distance from the source vertex s to every node v ∈ V. Initialized to dist[s] = 0 and dist[v] = ∞ for all v ≠ s.
• Predecessor Map (prev[]): Records the immediate prior node along the optimal path, allowing full path reconstruction via backtracking once the destination is reached.
• Unvisited Set / Min-Priority Queue (Q): Manages the pool of candidate vertices pending evaluation, prioritizing nodes with the lowest tentative distance.

At each step of the algorithm, the vertex u possessing the minimum tentative distance is extracted from Q. The algorithm then inspects all outgoing edges (u, v) ∈ E directed towards unvisited neighbors v. This evaluation step is formally termed Edge Relaxation:

// Edge Relaxation Formula
if (dist[u] + w(u, v) < dist[v]) {
    dist[v] = dist[u] + w(u, v);
    prev[v] = u;
    priorityQueue.decreaseKey(v, dist[v]);
}

Once all adjacent edges from node u have been evaluated, node u is permanently removed from the unvisited set. Because all edge weights are strictly non-negative, any alternative unvisited route to u must pass through an unvisited node whose current distance is already greater than or equal to dist[u], mathematically guaranteeing that dist[u] is optimal.

3. Asymptotic Time and Space Complexity Analysis

The algorithmic performance of Dijkstra's algorithm depends critically on the underlying data structures chosen to represent the graph and the priority queue:

• Dense Graph with Array / Adjacency Matrix: If vertices are stored in a simple linear array or matrix, finding the minimum element requires an O(V) scan across all unvisited vertices on each iteration. Since each vertex is extracted once and every edge is relaxed once, the overall time complexity is:

  Time: O(V² + E) = O(V²)

  This approach is asymptotically optimal for exceptionally dense graphs where E ≈ V².
• Sparse Graph with Min-Binary Heap / Priority Queue: For real-world sparse graphs (such as road networks where each intersection connects to only 3-5 roads on average, meaning E ≪ V²), extracting the minimum vertex takes O(log V) time, and each edge relaxation requires an O(log V) key decrease operation:

  Time: O((V + E) log V)

• Theoretical Bound with Fibonacci Heap: A Fibonacci heap permits O(1) amortized decrease-key operations and O(log V) minimum extractions, achieving a theoretical runtime of:

  Time: O(E + V log V)

• Space Complexity: The algorithm requires O(V) auxiliary memory to store the distance array, predecessor map, and priority queue pointers, plus O(V + E) to represent the graph adjacency list.

4. Real-World Engineering Applications: Network Routing & Geo-Navigation

Dijkstra's shortest path formulation powers core infrastructure across modern technological ecosystems:

1. Internet Protocol Link-State Routing: Major interior gateway routing protocols—specifically OSPF (Open Shortest Path First) and IS-IS (Intermediate System to Intermediate System)—run distributed variants of Dijkstra's algorithm inside enterprise core routers. Every router maintains a synchronized topological link-state database (LSDB) and computes the optimal packet forwarding path to all subnet prefixes.
2. Global Positioning System (GPS) Road Navigation: Digital mapping engines (such as Google Maps and OpenStreetMap) model continental road networks as massive graphs with millions of intersections and road segments. Augmented variants of Dijkstra's algorithm (such as bidirectional search, A* heuristics, and Contraction Hierarchies) compute real-time driving turn-by-turn routes in milliseconds.
3. Telecom Fiber & Electrical Grid Distribution: Telecommunication carriers and power distribution utilities utilize shortest path algorithms to model fiber-optic transmission latencies and power transmission cable impedances.
4. Video Game AI Pathfinding: Game engines compute non-player character (NPC) navigation across polygonal navigation meshes (navmeshes) using shortest path solvers to evade obstacles dynamically.

5. Step-by-Step Developer Implementation: Dijkstra in TypeScript

The following self-contained TypeScript/JavaScript implementation demonstrates how to implement Dijkstra's algorithm using a production-grade Min-Priority Queue structure:

interface Edge {
  to: string;
  weight: number;
}

type Graph = Record<string, Edge[]>;

interface ShortestPathResult {
  distances: Record<string, number>;
  previous: Record<string, string | null>;
  path: string[];
  totalDistance: number;
}

function dijkstra(graph: Graph, startNode: string, endNode: string): ShortestPathResult {
  const distances: Record<string, number> = {};
  const previous: Record<string, string | null> = {};
  const unvisited = new Set<string>();

  // 1. Initialization Phase
  for (const node in graph) {
    distances[node] = node === startNode ? 0 : Infinity;
    previous[node] = null;
    unvisited.add(node);
  }

  // 2. Traversal & Edge Relaxation Phase
  while (unvisited.size > 0) {
    // Find unvisited node with lowest tentative distance
    let currNode: string | null = null;
    let minDistance = Infinity;

    for (const node of unvisited) {
      if (distances[node] < minDistance) {
        minDistance = distances[node];
        currNode = node;
      }
    }

    // If unreachable or destination reached, terminate loop
    if (!currNode || minDistance === Infinity || currNode === endNode) {
      break;
    }

    unvisited.delete(currNode);

    // Inspect and relax adjacent edges
    for (const edge of graph[currNode] || []) {
      if (unvisited.has(edge.to)) {
        const alt = distances[currNode] + edge.weight;
        if (alt < distances[edge.to]) {
          distances[edge.to] = alt;
          previous[edge.to] = currNode;
        }
      }
    }
  }

  // 3. Path Backtracking Phase
  const path: string[] = [];
  let curr: string | null = endNode;

  while (curr !== null) {
    path.unshift(curr);
    curr = previous[curr];
  }

  return {
    distances,
    previous,
    path: path[0] === startNode ? path : [],
    totalDistance: distances[endNode]
  };
}