Dijkstra's Algorithm

@dijkstras_algorithm

Dijkstra's Algorithm finds the shortest path from one starting node to all other nodes in a graph by always expanding the currently closest node first.

Pseudo-code
function dijkstra(graph, source):

  # Step 1: Initialize distances and previous nodes
  for each node in graph:
    dist[node] = INF
    prev[node] = null

  dist[source] = 0

  # Step 2: Create priority queue
  pq = empty priority queue
  pq.insert(source, 0)

  visited = empty set

  # Step 3: Process nodes
  while pq is not empty:

    current = pq.extract_min()

    if current in visited:
      continue

    visited.add(current)

    # Step 4: Check all neighbors
    for each neighbor of current:

      distance = dist[current] + weight(current, neighbor)

      # Step 5: Relaxation step
      if distance < dist[neighbor]:
        dist[neighbor] = distance
        prev[neighbor] = current
        pq.insert(neighbor, distance)

  return dist, prev
  • dist A map of distances where dist[node] stores the shortest known distance from the start node to that node.
  • prev A map of previous nodes used to reconstruct the shortest path (like breadcrumbs).
  • pq A priority queue that always gives you the node with the smallest distance first.
  • visited A set of nodes already finalized, meaning we already found their shortest path.
  • INF A very large number representing infinity (used to initialize distances).
  • graph The input structure containing nodes and edges with weights (distances).
Recipe Steps
1

Start at your location — Imagine you are at home and want to reach every place using the shortest path.

2

Write down the distance to every place as infinity, except your home which is 0.

3

Always go to the closest place next — Pick the location with the smallest known distance.

4

From that place, check all neighboring roads and see if going through this place is shorter than what you knew before.

5

Update distances if you found a shorter route, and repeat until all places are processed.

Questions & Answers

Always expand the closest unvisited node first.

It is the process of updating a shorter distance when a better path is found.

To efficiently get the next closest node.

We update both dist[node] and prev[node].
- Time complexity is O((V + E) log V) with a priority queue.
- Does not work with negative weights.
- Tip: Think of it as spreading out like a wave from the start node.
- Common mistake: Not checking if a node was already visited.
- You can reconstruct the shortest path by following the prev map backwards.

Related Algorithms
Backtracking

Backtracking is a problem-solving technique used in algorithms to find a solution by exploring all possible solutions and retracting when a dead end is reached. It's often used for solving puzzles, finding paths, or scheduling tasks.

View
Bellman-Ford Algorithm

The Bellman-Ford algorithm finds the shortest path from a source node to all other nodes, even when there are negative edge weights. It works by repeatedly improving distance estimates.

View
Binary Search

Binary Search is a very fast algorithm used to find a value in a sorted list by repeatedly cutting the search space in half until the item is found or nothing is left.

View