Djikstra

Djikstra.java

boolean[] visited = new boolean[N+1];
// [distance, toNode]
PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> (a[0] - b[0]));
pq.add(new int[]{0, startNode});
while(!pq.isEmpty()) {
  int[] current = pq.poll();
  int node = current[1];
  int dist = current[0];
  // if reached target node, return dist, or if task is to cover entire graph continue
  if(!visited[node]) {
    visited[node] = true;
    Map<Integer, Integer> connections = graph.get(node);
    if(connections != null) {
      for(int next: connections.keySet()) {
        pq.add(new int[]{dist + connections.get(next), next});
      }
    }
  }
}