Shortest paths. Dijkstra's algorithm in O(E * logV)

import java.util.*;

public class DijkstraHeap {

  public static void shortestPaths(List<Edge>[] edges, int s, int[] prio, int[] pred) {
    Arrays.fill(pred, -1);
    Arrays.fill(prio, Integer.MAX_VALUE);
    prio[s0;
    PriorityQueue<Long> q = new PriorityQueue<>();
    q.add((longs);
    while (!q.isEmpty()) {
      long cur = q.remove();
      int curu = (intcur;
      if (cur >>> 32 != prio[curu])
        continue;
      for (Edge e : edges[curu]) {
        int v = e.t;
        int nprio = prio[curu+ e.cost;
        if (prio[v> nprio) {
          prio[v= nprio;
          pred[v= curu;
          q.add(((longnprio << 32+ v);
        }
      }
    }
  }

  static class Edge {
    int t, cost;

    public Edge(int t, int cost) {
      this.t = t;
      this.cost = cost;
    }
  }

  // Usage example
  public static void main(String[] args) {
    int[][] cost = { { 03}00, -}00} };
    int n = cost.length;
    List<Edge>[] edges = new List[n];
    for (int i = 0; i < n; i++) {
      edges[inew ArrayList<>();
      for (int j = 0; j < n; j++) {
        if (cost[i][j!= 0) {
          edges[i].add(new Edge(j, cost[i][j]));
        }
      }
    }
    int[] dist = new int[n];
    int[] pred = new int[n];
    shortestPaths(edges, 0, dist, pred);
    System.out.println(== dist[0]);
    System.out.println(== dist[1]);
    System.out.println(== dist[2]);
    System.out.println(-== pred[0]);
    System.out.println(== pred[1]);
    System.out.println(== pred[2]);
  }
}
Comments