# InitList < int[] > [] adjList = new ArrayList[n];for (int from = 0; from < n; from++) adjList[from] = new ArrayList < > ();# Convert from Adjacency Matrixfor (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();}