Dijkstra Algorithm

Definition

Definition

Dijkstra's algorithm is a graph search algorithm that finds the shortest path between nodes in a graph, particularly for graphs with non-negative edge weights

Explanation

Set the distance from the start node to all other nodes as infinite, and the distance to itself as 0. We mark all nodes as unvisited and set the initial node as the current node. Then, for the current node, we assess each of its neighbors and compute their tentative distances through the current node. We compare these newly calculated tentative distances to the current assigned values and update them if a smaller distance is found. Afterward, we mark the current node as visited and remove it from the unvisited set. We check if the destination node has been visited or if the smallest tentative distance among the unvisited nodes is infinite; if so, the algorithm stops. Otherwise, we select the unvisited node with the smallest tentative distance, set it as the new current node, and repeat the process

Guidance

• Start from the source node
• Assign tentative distances to all nodes. Initialize the source node distance as 0 and all others as infinite
• Mark all nodes as unvisited
• Set the current node as the source node
• For each neighboring node of the current node
  • calculate the tentative distance from the source node through the current node
  • if this distance is less than the current assigned distance, update it
  • Mark the current node as visited
  • If the destination node has been visited or if the smallest tentative distance among the unvisited nodes is infinite, stop. Otherwise, select the unvisited node with the smallest tentative distance as the new current node and repeat

Tips

• keep track of the shortest distance from the source node to each node
• use a priority queue or heap to efficiently select the node with the smallest tentative distance
• ensure that the graph doesn't contain negative edge weights, as Dijkstra's algorithm doesn't work correctly with negative weights

Practice

Practice

Dijkstra(Graph, source):
    dist[source] := 0
    for each vertex v in Graph:
        if v ≠ source
            dist[v] := infinity
        add v to unvisited set

    while unvisited set is not empty:
        current := vertex in unvisited set with smallest distance
        remove current from unvisited set
        for each neighbor v of current:
            alt := dist[current] + weight(current, v)
            if alt < dist[v]:
                dist[v] := alt

    return dist

Solution

package main

import (
    "container/heap"
    "math"
)

type Edge struct {
    to     int
    weight int
}

type Node struct {
    id   int
    dist int
}

type PriorityQueue []*Node

func (pq PriorityQueue) Len() int { return len(pq) }
func (pq PriorityQueue) Less(i, j int) bool {
    return pq[i].dist < pq[j].dist
}
func (pq PriorityQueue) Swap(i, j int) {
    pq[i], pq[j] = pq[j], pq[i]
}
func (pq *PriorityQueue) Push(x interface{}) {
    item := x.(*Node)
    *pq = append(*pq, item)
}
func (pq *PriorityQueue) Pop() interface{} {
    old := *pq
    n := len(old)
    item := old[n-1]
    *pq = old[0 : n-1]
    return item
}

func dijkstra(graph [][]Edge, source int) []int {
    n := len(graph)
    dist := make([]int, n)
    for i := range dist {
        dist[i] = math.MaxInt32
    }
    dist[source] = 0

    pq := make(PriorityQueue, 0)
    heap.Init(&pq)
    heap.Push(&pq, &Node{source, 0})

    for pq.Len() > 0 {
        node := heap.Pop(&pq).(*Node)
        u := node.id
        if dist[u] < node.dist {
            continue
        }
        for _, edge := range graph[u] {
            if alt := dist[u] + edge.weight; alt < dist[edge.to] {
                dist[edge.to] = alt
                heap.Push(&pq, &Node{edge.to, alt})
            }
        }
    }
    return dist
}

import java.util.*;

class Dijkstra {

  static int[] dijkstra(List<List<Edge>> graph, int source) {
    int n = graph.size();
    int[] dist = new int[n];
    Arrays.fill(dist, Integer.MAX_VALUE);
    dist[source] = 0;

    PriorityQueue<Node> pq = new PriorityQueue<>();
    pq.add(new Node(source, 0));

    while (!pq.isEmpty()) {
      Node node = pq.poll();
      int u = node.id;
      if (dist[u] < node.dist) {
        continue;
      }
      for (Edge edge : graph.get(u)) {
        int alt = dist[u] + edge.weight;
        if (alt < dist[edge.to]) {
          dist[edge.to] = alt;
          pq.add(new Node(edge.to, alt));
        }
      }
    }
    return dist;
  }

  static class Edge {

    int to, weight;

    Edge(int to, int weight) {
      this.to = to;
      this.weight = weight;
    }
  }

  static class Node implements Comparable<Node> {

    int id, dist;

    Node(int id, int dist) {
      this.id = id;
      this.dist = dist;
    }

    public int compareTo(Node other) {
      return Integer.compare(this.dist, other.dist);
    }
  }
}

class PriorityQueue {
  constructor() {
    this.heap = [];
  }

  enqueue(node) {
    this.heap.push(node);
    this.bubbleUp();
  }

  dequeue() {
    const min = this.heap[0];
    const end = this.heap.pop();
    if (this.heap.length > 0) {
      this.heap[0] = end;
      this.sinkDown();
    }
    return min;
  }

  bubbleUp() {
    let index = this.heap.length - 1;
    const node = this.heap[index];
    while (index > 0) {
      let parentIndex = Math.floor((index - 1) / 2);
      let parent = this.heap[parentIndex];
      if (node.dist >= parent.dist) {
        break;
      }
      this.heap[parentIndex] = node;
      this.heap[index] = parent;
      index = parentIndex;
    }
  }

  sinkDown() {
    let index = 0;
    const length = this.heap.length;
    const node = this.heap[0];
    while (true) {
      let leftChildIndex = 2 * index + 1;
      let rightChildIndex = 2 * index + 2;
      let leftChild, rightChild;
      let swap = null;

      if (leftChildIndex < length) {
        leftChild = this.heap[leftChildIndex];
        if (leftChild.dist < node.dist) {
          swap = leftChildIndex;
        }
      }
      if (rightChildIndex < length) {
        rightChild = this.heap[rightChildIndex];
        if (
          (swap === null && rightChild.dist < node.dist) ||
          (swap !== null && rightChild.dist < leftChild.dist)
        ) {
          swap = rightChildIndex;
        }
      }
      if (swap === null) {
        break;
      }
      this.heap[index] = this.heap[swap];
      this.heap[swap] = node;
      index = swap;
    }
  }

  isEmpty() {
    return this.heap.length === 0;
  }
}

class Dijkstra {
  constructor() {
    this.graph = [];
  }

  addEdge(from, to, weight) {
    if (!this.graph[from]) {
      this.graph[from] = [];
    }
    this.graph[from].push({ to, weight });
  }

  dijkstra(source) {
    const n = this.graph.length;
    const dist = Array(n).fill(Infinity);
    dist[source] = 0;

    const pq = new PriorityQueue();
    pq.enqueue({ id: source, dist: 0 });

    while (!pq.isEmpty()) {
      const node = pq.dequeue();
      const u = node.id;
      if (dist[u] < node.dist) {
        continue;
      }
      for (const edge of this.graph[u] || []) {
        const alt = dist[u] + edge.weight;
        if (alt < dist[edge.to]) {
          dist[edge.to] = alt;
          pq.enqueue({ id: edge.to, dist: alt });
        }
      }
    }
    return dist;
  }
}

import java.util.*

class Edge(val to: Int, val weight: Int)

class Node(val id: Int, val dist: Int) : Comparable<Node> {
    override fun compareTo(other: Node): Int {
        return this.dist.compareTo(other.dist)
    }
}

fun dijkstra(graph: List<List<Edge>>, source: Int): IntArray {
    val n = graph.size
    val dist = IntArray(n) { Int.MAX_VALUE }
    dist[source] = 0

    val pq = PriorityQueue<Node>()
    pq.add(Node(source, 0))

    while (pq.isNotEmpty()) {
        val node = pq.poll()
        val u = node.id
        if (dist[u] < node.dist) continue
        for (edge in graph[u]) {
            val alt = dist[u] + edge.weight
            if (alt < dist[edge.to]) {
                dist[edge.to] = alt
                pq.add(Node(edge.to, alt))
            }
        }
    }
    return dist
}

import heapq

class Dijkstra:
    def __init__(self):
        self.graph = []

    def add_edge(self, frm, to, weight):
        if len(self.graph) <= frm:
            self.graph += [[]] * (frm - len(self.graph) + 1)
        self.graph[frm].append((to, weight))

    def dijkstra(self, source):
        n = len(self.graph)
        dist = [float('inf')] * n
        dist[source] = 0

        pq = [(0, source)]

        while pq:
            d, u = heapq.heappop(pq)
            if d > dist[u]:
                continue
            for v, w in self.graph[u]:
                if alt := dist[u] + w < dist[v]:
                    dist[v] = alt
                    heapq.heappush(pq, (alt, v))
        return dist

use std::cmp::Ordering;
use std::collections::BinaryHeap;

#[derive(Debug, Clone, Copy, Eq, PartialEq)]
struct Edge {
    to: usize,
    weight: i32,
}

#[derive(Debug, Clone, Copy, Eq, PartialEq)]
struct Node {
    id: usize,
    dist: i32,
}

impl Ord for Node {
    fn cmp(&self, other: &Self) -> Ordering {
        other.dist.cmp(&self.dist)
    }
}

impl PartialOrd for Node {
    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
        Some(self.cmp(other))
    }
}

fn dijkstra(graph: &[Vec<Edge>], source: usize) -> Vec<i32> {
    let n = graph.len();
    let mut dist = vec![i32::MAX; n];
    dist[source] = 0;

    let mut pq = BinaryHeap::new();
    pq.push(Node { id: source, dist: 0 });

    while let Some(Node { id: u, dist: _ }) = pq.pop() {
        for edge in &graph[u] {
            let alt = dist[u] + edge.weight;
            if alt < dist[edge.to] {
                dist[edge.to] = alt;
                pq.push(Node { id: edge.to, dist: alt });
            }
        }
    }
    dist
}

class PriorityQueue<T> {
  heap: { dist: number; node: T }[];

  constructor() {
    this.heap = [];
  }

  enqueue(node: T, dist: number) {
    this.heap.push({ dist, node });
    this.bubbleUp();
  }

  dequeue() {
    const min = this.heap[0];
    const end = this.heap.pop();
    if (this.heap.length > 0) {
      this.heap[0] = end;
      this.sinkDown();
    }
    return min?.node;
  }

  bubbleUp() {
    let index = this.heap.length - 1;
    const node = this.heap[index];
    while (index > 0) {
      let parentIndex = Math.floor((index - 1) / 2);
      let parent = this.heap[parentIndex];
      if (node.dist >= parent.dist) break;
      this.heap[parentIndex] = node;
      this.heap[index] = parent;
      index = parentIndex;
    }
  }

  sinkDown() {
    let index = 0;
    const length = this.heap.length;
    const node = this.heap[0];
    while (true) {
      let leftChildIndex = 2 * index + 1;
      let rightChildIndex = 2 * index + 2;
      let leftChild, rightChild;
      let swap = null;

      if (leftChildIndex < length) {
        leftChild = this.heap[leftChildIndex];
        if (leftChild.dist < node.dist) {
          swap = leftChildIndex;
        }
      }
      if (rightChildIndex < length) {
        rightChild = this.heap[rightChildIndex];
        if (
          (swap === null && rightChild.dist < node.dist) ||
          (swap !== null && rightChild.dist < leftChild.dist)
        ) {
          swap = rightChildIndex;
        }
      }
      if (swap === null) break;
      this.heap[index] = this.heap[swap];
      this.heap[swap] = node;
      index = swap;
    }
  }

  isEmpty() {
    return this.heap.length === 0;
  }
}

class Dijkstra {
  graph: { to: number; weight: number }[][];

  constructor() {
    this.graph = [];
  }

  addEdge(from: number, to: number, weight: number) {
    if (!this.graph[from]) {
      this.graph[from] = [];
    }
    this.graph[from].push({ to, weight });
  }

  dijkstra(source: number): number[] {
    const n = this.graph.length;
    const dist = Array(n).fill(Infinity);
    dist[source] = 0;

    const pq = new PriorityQueue<number>();
    pq.enqueue(source, 0);

    while (!pq.isEmpty()) {
      const { node: u, dist: d } = pq.dequeue()!;
      if (d > dist[u]) continue;
      for (const edge of this.graph[u] || []) {
        const alt = dist[u] + edge.weight;
        if (alt < dist[edge.to]) {
          dist[edge.to] = alt;
          pq.enqueue(edge.to, alt);
        }
      }
    }
    return dist;
  }
}