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[s] = 0;
PriorityQueue<Long> q = new PriorityQueue<>();
q.add((long) s);
while (!q.isEmpty()) {
long cur = q.remove();
int curu = (int) cur;
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(((long) nprio << 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 = { { 0, 3, 2 }, { 0, 0, -2 }, { 0, 0, 0 } };
int n = cost.length;
List<Edge>[] edges = new List[n];
for (int i = 0; i < n; i++) {
edges[i] = new 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(0 == dist[0]);
System.out.println(3 == dist[1]);
System.out.println(1 == dist[2]);
System.out.println(-1 == pred[0]);
System.out.println(0 == pred[1]);
System.out.println(1 == pred[2]);
}
}
|
|
|