Đang tải…
Đang tải…
Giống Dijkstra nhưng dùng hàm heuristic kéo hướng tìm về đích — nên duyệt ít ô hơn nhiều mà vẫn cho đường ngắn nhất.
Khởi tạo tập mở với điểm đầu.
1g[start] = 0;2open.add(new int[]{h(start), start});3while (!open.isEmpty()) {4 int node = open.poll()[1];5 if (settled[node]) continue;6 settled[node] = true;7 if (node == goal) return buildPath();8 for (int nb : neighbors(node)) {9 int ng = g[node] + cost(nb);10 if (ng < g[nb]) {11 g[nb] = ng; parent[nb] = node;12 open.add(new int[]{ng + h(nb), nb});13 }14 }15}