Dijkstra Algo(How to pronouce) is a way to find the shortest path between two points in a graph with:
Directed graph: edge (1, 3) != edge (3, 1)
potential circles: edge (1, 3) (3, 2), (2, 1)
positive weights. each edge must have positive weight.

Leetcode Problems: 743, 1102

public class DijkstraAlgo {
    int[] dist;    //dist[i] means the shortest path from starting point to node i; 
    int[] preNode; //the previous node for shortest path, we could build the path with this record;
    PriorityQueue<Integer> pq; 
    
   /**
   edges -> [[0,3,2],[1,3,4]]   [edge From, edge To, edge Cost]
   start -> start point of the graph
   N     -> total node number in the graph
   */
    public int[] findShortestPath(int[][] edges, int start, int N) {
        List<int[]>[] graph = buildGraph(edges, N); 
        dist = new int[N];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[start] = 0; 
        
        preNode = new int[N];
        Arrays.fill(preNode, -1); 
        preNode[start] = start;

        pq = new PrirorityQueue<>((a, b) -> {return dist[a] - dist[b];});
        pq.add(start);
        
        while (!pq.isEmpty()) {
            int curr = pq.poll();
            int cost = dist[curr];
            
            for (int[] next: graph[curr]) { // visit all the adj, int[] next -> [curr, next, cost]
                int nextIdx = next[1], edgeCost = next[2];
                if (cost + edgeCost < dist[nextIdx]) {
                    if (preNode[nextIdx] != -1) {
                       pq.remove(nextIdx);
                    }
                    dist[nextIdx] = cost + edgeCost;
                    preNode[nextIdx] = curr;
                    pq.add(nextIdx);
                }
            }
        }

        return dist;
    }

    /*for each node, find its adjcent(next) nodes.*/
    private List<int[]>[] buildGraph(int[][] edges, int N) {
        List<int[]>[] graph = new List[N];
        for (int i = 0; i < N; i++) graph[i] = new ArrayList<>();
        for (int[] edge: edges) graph[edge[0]].add(edge);
        return graph;
    }
}