Loading…
Loading…
Expands the closest unsettled node first using a priority queue, giving the shortest path even when cells have different costs (weights).
Start distance = 0.
1dist[start] = 0;2pq.add(new int[]{0, start});3while (!pq.isEmpty()) {4 int[] top = pq.poll(); int node = top[1];5 if (settled[node]) continue;6 settled[node] = true;7 if (node == goal) return buildPath();8 for (int nb : neighbors(node)) {9 int nd = dist[node] + cost(nb);10 if (nd < dist[nb]) {11 dist[nb] = nd; parent[nb] = node;12 pq.add(new int[]{nd, nb});13 }14 }15}