Bagian 2: Implementasi Dijkstra

Grid telah dimodelkan sebagai graph berbobot seragam. Sekarang kita menjalankan Dijkstra untuk menghitung jarak terpendek dari start ke setiap sel. Pada bagian ini fokus adalah algoritma inti: inisialisasi dist[] dengan infinity, push start ke priority queue, lalu loop relaksasi sampai queue kosong. Rekonstruksi jalur menyusul pada Bagian 3.

Inisialisasi `dist` 2D #

Karena grid 2D, dist juga 2D — std::vector<std::vector<int>> berukuran rows × cols. Nilai awal INF (konstanta besar), kecuali dist[start] = 0.

cpp
const int INF = 1'000'000'000;

std::vector<std::vector<int>> dist(g.rows, std::vector<int>(g.cols, INF));
dist[start.row][start.col] = 0;

Min-Heap dengan `std::priority_queue` #

std::priority_queue default adalah max-heap. Untuk min-heap, kita pakai std::greater<std::pair<int, Cell>> sebagai comparator. Pair disusun (dist, cell) sehingga perbandingan default membandingkan dist lebih dulu.

cpp
using State = std::pair<int, Cell>;
std::priority_queue<State, std::vector<State>, std::greater<State>> pq;
pq.push({0, start});

Lazy Deletion #

Saat dist[v] diperbarui, kita push entry baru (dist_baru, v). Entry lama (dist_lama, v) tetap ada di heap. Saat entry lama muncul di top, kita cek apakah dist di array sudah lebih kecil — bila ya, skip.

cpp
while (!pq.empty()) {
    auto [d, u] = pq.top(); pq.pop();
    if (d > dist[u.row][u.col]) continue;   // stale entry
    // ... relaksasi neighbors
}

Program Lengkap Bagian 2 #

cpp
#include <iostream>
#include <queue>
#include <vector>

struct Cell {
    int row, col;
    bool operator==(const Cell& o) const { return row == o.row && col == o.col; }
    bool operator<(const Cell& o) const {
        return row != o.row ? row < o.row : col < o.col;
    }
};

struct Grid {
    std::vector<std::string> cells;
    int rows, cols;
    Grid(std::vector<std::string> g) : cells(std::move(g)) {
        rows = (int)cells.size();
        cols = rows > 0 ? (int)cells[0].size() : 0;
    }
    bool inBounds(int r, int c) const { return r >= 0 && r < rows && c >= 0 && c < cols; }
    bool walkable(int r, int c) const {
        if (!inBounds(r, c)) return false;
        return cells[r][c] != '#';
    }
};

std::vector<Cell> neighbors(const Grid& g, const Cell& c) {
    static const int dr[] = {-1, 1, 0, 0};
    static const int dc[] = {0, 0, -1, 1};
    std::vector<Cell> result;
    for (int i = 0; i < 4; ++i) {
        int nr = c.row + dr[i], nc = c.col + dc[i];
        if (g.walkable(nr, nc)) result.push_back({nr, nc});
    }
    return result;
}

const int INF = 1'000'000'000;

std::vector<std::vector<int>> dijkstra(
        const Grid& g, const Cell& start) {
    std::vector<std::vector<int>> dist(g.rows, std::vector<int>(g.cols, INF));
    using State = std::pair<int, Cell>;
    std::priority_queue<State, std::vector<State>, std::greater<State>> pq;

    dist[start.row][start.col] = 0;
    pq.push({0, start});

    while (!pq.empty()) {
        auto [d, u] = pq.top(); pq.pop();
        if (d > dist[u.row][u.col]) continue;   // stale
        for (const auto& nb : neighbors(g, u)) {
            int nd = d + 1;   // bobot seragam 1
            if (nd < dist[nb.row][nb.col]) {
                dist[nb.row][nb.col] = nd;
                pq.push({nd, nb});
            }
        }
    }
    return dist;
}

void printDist(const std::vector<std::vector<int>>& dist, const Grid& g) {
    std::cout << "Dist dari start:\n";
    for (int r = 0; r < g.rows; ++r) {
        for (int c = 0; c < g.cols; ++c) {
            if (g.cells[r][c] == '#') std::cout << "  # ";
            else if (dist[r][c] == INF) std::cout << "  . ";
            else std::cout << std::setw(3) << dist[r][c] << " ";
        }
        std::cout << "\n";
    }
}

int main() {
    Grid g({
        ".....",
        ".###.",
        ".S.#.",
        "...#.",
        "...G."
    });
    Cell start = {2, 1};
    auto dist = dijkstra(g, start);
    printDist(dist, g);
    std::cout << "\nJarak start -> goal (4,4) = "
              << (dist[4][4] == INF ? -1 : dist[4][4]) << "\n";
    return 0;
}

Output yang Dihasilkan:

text
Dist dari start:
  3   4   5   6   7 
  2   #   #   #   8 
  1   0   1   #   7 
  2   1   2   #   6 
  3   2   3   4   5 

Jarak start -> goal (4,3) = 4

Perhatikan posisi G di grid: baris "...G." memiliki G pada kolom 3 (bukan 4). Dijkstra mengisi seluruh tabel dist — kolom yang ditandai # adalah rintangan, dan sel yang tidak terjangkau akan tetap INF (ditampilkan sebagai . pada output). Jarak terpendek dari start (2,1) ke goal (4,3) adalah 4 langkah.

Bedah Baris Penting #

const int INF = 1'000'000'000: konstanta besar dengan digit separator ' (C++14) agar mudah dibaca. Nilai harus cukup besar agar tidak overflow saat dijumlah dengan bobot edge (1), tetapi tidak boleh sampai INT_MAX karena d + 1 bisa overflow.
std::pair<int, Cell> sebagai State: pair diurutkan berdasarkan elemen pertama (dist). std::greater membuat heap mengeluarkan elemen dengan dist terkecil lebih dulu — min-heap.
if (d > dist[u.row][u.col]) continue: lazy deletion. Bila entry heap menunjukkan d lebih besar dari dist di array, artinya entry ini sudah kedaluwarsa — sudah ada pembaruan yang lebih baik. Skip tanpa memproses neighbors.
int nd = d + 1: bobot edge seragam 1. Untuk bobot variabel, ganti 1 dengan lookup weight(u, nb).
if (nd < dist[nb.row][nb.col]): kondisi relaksasi. Hanya push ke heap bila ditemukan jarak lebih kecil. Tanpa check ini, heap dipenuhi entry yang tidak memperbaiki hasil — pemborosan waktu.

Analisis Kompleksitas #

Aspek	Kompleksitas	Catatan
Inisialisasi `dist`	O(V)	V = rows × cols
Push start	O(1)	satu operasi
Loop utama	O((V+E) log V)	setiap edge di-relax paling sekali per perbaikan
Memory	O(V + E)	dist array + heap
Best case (goal dekat)	O(V log V)	early exit bila dihentikan saat goal pop

Kompilasi dan Pengujian #

bash
g++ -std=c++17 -O2 -Wall -Wextra -o dijkstra.bin dijkstra.cpp
./dijkstra.bin

Verifikasi bahwa dist ke sel goal (4,3) adalah 4. Pada Bagian 3, kita merekonstruksi jalur dari dist ini menggunakan array parent.