Kata: Dijkstra's Shortest Path

Table of contents

Problem Statement

Implement Dijkstra’s algorithm to find the shortest path in a weighted, directed graph:

1. Build a weighted graph with addEdge(from, to, weight)
2. Implement shortestPath(start, end) returning the distance and path
3. Handle the case where no path exists

Constraint: All edge weights must be non-negative.

Concepts

Dijkstra’s algorithm finds the shortest path from a source to all other vertices. It uses a priority queue (min-heap) to always process the vertex with the smallest known distance.

Algorithm:

1. Set distance to start = 0, all others = infinity
2. Add start to the priority queue
3. While the queue is not empty:
   • Extract the vertex with minimum distance
   • For each neighbor, if a shorter path is found through the current vertex, update the distance and add to queue

PHP: SplPriorityQueue provides a built-in priority queue. See PHP Core Concepts.

Python: heapq module provides heap operations on regular lists. See Python Core Concepts.

Boilerplate

TypeScript

// dijkstra.ts
type WeightedGraph = Map<string, Array<{ vertex: string; weight: number }>>;

function dijkstra(
  graph: WeightedGraph,
  start: string,
  end: string
): { distance: number; path: string[] } | null {
  // TODO
  return null;
}

Hints

Solution

TypeScript

type WeightedGraph = Map<string, Array<{ vertex: string; weight: number }>>;

function dijkstra(
  graph: WeightedGraph,
  start: string,
  end: string
): { distance: number; path: string[] } | null {
  const distances = new Map<string, number>();
  const previous = new Map<string, string | null>();
  const visited = new Set<string>();

  // Initialize
  for (const vertex of graph.keys()) {
    distances.set(vertex, Infinity);
    previous.set(vertex, null);
  }
  distances.set(start, 0);

  // Simple priority queue using sorted array
  const queue: Array<{ vertex: string; distance: number }> = [
    { vertex: start, distance: 0 },
  ];

  while (queue.length > 0) {
    // Extract minimum
    queue.sort((a, b) => a.distance - b.distance);
    const { vertex: current } = queue.shift()!;

    if (visited.has(current)) continue;
    visited.add(current);

    // Early termination
    if (current === end) break;

    for (const { vertex: neighbor, weight } of graph.get(current) ?? []) {
      if (visited.has(neighbor)) continue;

      const newDist = distances.get(current)! + weight;
      if (newDist < distances.get(neighbor)!) {
        distances.set(neighbor, newDist);
        previous.set(neighbor, current);
        queue.push({ vertex: neighbor, distance: newDist });
      }
    }
  }

  // Reconstruct path
  const distance = distances.get(end)!;
  if (distance === Infinity) return null;

  const path: string[] = [];
  let current: string | null = end;
  while (current !== null) {
    path.unshift(current);
    current = previous.get(current) ?? null;
  }

  return { distance, path };
}

Python

import heapq
from collections import defaultdict

WeightedGraph = defaultdict[str, list[tuple[str, float]]]

def dijkstra(
    graph: WeightedGraph,
    start: str,
    end: str,
) -> tuple[float, list[str]] | None:
    distances: dict[str, float] = {v: float("inf") for v in graph}
    distances[start] = 0
    previous: dict[str, str | None] = {v: None for v in graph}
    visited: set[str] = set()

    # Min-heap: (distance, vertex)
    queue: list[tuple[float, str]] = [(0, start)]

    while queue:
        dist, current = heapq.heappop(queue)

        if current in visited:
            continue
        visited.add(current)

        if current == end:
            break

        for neighbor, weight in graph[current]:
            if neighbor in visited:
                continue
            new_dist = dist + weight
            if new_dist < distances.get(neighbor, float("inf")):
                distances[neighbor] = new_dist
                previous[neighbor] = current
                heapq.heappush(queue, (new_dist, neighbor))

    if distances.get(end, float("inf")) == float("inf"):
        return None

    # Reconstruct path
    path: list[str] = []
    current_node: str | None = end
    while current_node is not None:
        path.append(current_node)
        current_node = previous.get(current_node)
    path.reverse()

    return distances[end], path

PHP

function dijkstra(array $graph, string $start, string $end): ?array {
    $distances = [];
    $previous = [];

    foreach (array_keys($graph) as $vertex) {
        $distances[$vertex] = PHP_INT_MAX;
        $previous[$vertex] = null;
    }
    $distances[$start] = 0;

    $queue = new SplPriorityQueue();
    $queue->setExtractFlags(SplPriorityQueue::EXTR_BOTH);
    $queue->insert($start, 0); // negative priority for min-heap behavior

    $visited = [];

    while (!$queue->isEmpty()) {
        $item = $queue->extract();
        $current = $item['data'];

        if (isset($visited[$current])) continue;
        $visited[$current] = true;

        if ($current === $end) break;

        foreach ($graph[$current] ?? [] as [$neighbor, $weight]) {
            if (isset($visited[$neighbor])) continue;
            $newDist = $distances[$current] + $weight;
            if ($newDist < $distances[$neighbor]) {
                $distances[$neighbor] = $newDist;
                $previous[$neighbor] = $current;
                $queue->insert($neighbor, -$newDist); // negate for min-heap
            }
        }
    }

    if ($distances[$end] === PHP_INT_MAX) return null;

    $path = [];
    $current = $end;
    while ($current !== null) {
        array_unshift($path, $current);
        $current = $previous[$current];
    }

    return ['distance' => $distances[$end], 'path' => $path];
}

Complexity Analysis

For sparse graphs (E ~ V), a binary heap is optimal. For dense graphs (E ~ V^2), the simple sorted array can be competitive.

Cross-Language Notes

Python: The heapq module provides a min-heap on top of a regular list. It’s the standard choice for Dijkstra in Python. Note: heapq doesn’t support decrease-key, so we push duplicates and skip visited nodes.

PHP: SplPriorityQueue is a max-heap by default. Negate priorities to use it as a min-heap (as shown in the PHP solution). See PHP Core Concepts.

C++: std::priority_queue with std::greater gives a min-heap. The STL implementation is efficient and commonly used in competitive programming.

Limitation: Dijkstra fails with negative edge weights. For graphs with negative edges, use Bellman-Ford (O(VE)) or, for all-pairs shortest paths, Floyd-Warshall (O(V^3)).

See also: Kata: Graph Traversal for unweighted graph algorithms.