Dijkstra's Algorithm

Abstract

---

• Used to find the shortest path from any starting node to all other nodes in a Graph - Single Source Shortest Path on a Weighted Graph that is either Directed Graph or Undirected Graph

  
  

• Use Greedy Algorithm to improve the computation performance via Priority Queue

• Use Combinatorial Optimisation to obtain the shortest distance from the given node to all other nodes

Negative Edge

May not work if there are negative Edge

Java Code Templates

---

Construct Adjacency List

From Adjacency Matrix

# Init
List < int[] > [] adjList = new ArrayList[n];
for (int from = 0; from < n; from++) adjList[from] = new ArrayList < > ();
 
# Convert from Adjacency Matrix
for (int from = 0; from < n; from++) {
  int[] edges = adjMaxtrix[from];
  for (int to = 0; to < edges.length; to++) {
    int edgeWeight = edges[to];
    if (edgeWeight == 0 || from == to) continue;
    # Use this line to skip adding relationship between 2 nodes when there isn 't a valid relationship present
 
    adjList[from].add(new int[] {
      to,
      edgeWeight
    });
  }
}

Main Algorithm

class State {
  int id;
  int distFromStart;
 
  public State(int id, int distFromStart) {
    this.id = id;
    this.distFromStart = distFromStart;
  }
}
 
int[] dijkstra(int start, List < int[] > [] graph) {
  // DP Table (Integer.MAX_VALUE for minimization problems)
  int[] distTo = new int[graph.length];
  Arrays.fill(distTo, Integer.MAX_VALUE);
  distTo[start] = 0;
 
  // Greedy (min heap for minimization problems)
  PriorityQueue < State > pq = new PriorityQueue < > ((a, b) -> {
    return a.distFromStart - b.distFromStart;
  });
  pq.offer(new State(start, 0));
 
  while (!pq.isEmpty()) {
    State nodeState = pq.poll(); // Greedy approach: start from the smallest
    int nodeID = nodeState.id;
    int curDistFromStart = nodeState.distFromStart;
 
    // Skip when I already have a shorter path to reach the node
    if (distTo[nodeID] < curDistFromStart) continue;
 
    for (int[] neighbor: graph[nodeID]) {
      int nextNodeID = neighbor[0];
      int distToNextNode = curDistFromStart + neighbor[1];
 
      if (distToNextNode < distTo[nextNodeID]) { // Edge Relaxation, update dp table
        distTo[nextNodeID] = distToNextNode;
        pq.offer(new State(nextNodeID, distToNextNode));
      }
    }
  }
 
  return distTo;
}

Debugging Codes

Examine the node relationships of the adjacency list

for (int i = 0; i < n; i++) {
  List < int[] > n = adjList[i];
  System.out.printf("Outward edges from node %d: \n", i);
  for (int[] r: n) {
    System.out.println(Arrays.toString(r));
  }
  System.out.println();
}

Leetcode Question

---

• Byte-dance Mock Test (Product Recommendation)

Terminologies

---

Source Vertex

• The starting node

Edge Relaxation

• Update path for already known nodes as soon as we find a shorter path to reach it