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 or Non-Directed
• Use Greedy Algorithm to improve the computation performance via Priority Queue
• Use Dynamic Programming to obtain the shortest distance from the given node to all other nodes → Optimisation Problem via DP Table

Cons

---

Negative Edge

• May not work if there are negative Edge

Code Templates

---

Java

Main

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;
}

Construct Adjacency List

# 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});
	}
}

Debugging

• Examine the relationship of adjList

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