Pencarian Jalur

Aplikasi peta seperti Google Maps menghitung rute terpendek antara jutaan pasangan lokasi per detik. Game strategi mengarahkan unit melewati medan berliku. Robot warehouse menavigasi lorong sempit tanpa tabrakan. Di balik semua ini bekerja algoritma pencarian jalur yang kita pelajari pada bab graph — Dijkstra, BFS, A*. Pada Chapter ini kita akan menerapkan Dijkstra pada grid 2D dengan rintangan, lengkap dengan rekonstruksi jalur dan visualisasi. Tujuan akhirnya: memahami bahwa grid adalah graph implisit, dan bahwa memilih algoritma yang tepat antara Dijkstra, BFS, dan A* bergantung pada karakteristik masalah.

Grid sebagai Graph Implisit #

Grid 2D adalah graph berbobot dengan aturan sederhana: setiap sel adalah vertex, tetangga ortogonal (atas/bawah/kiri/kanan) adalah edge berbobot 1 (atau bobot khusus seperti medan berbeda). Rintangan (#) adalah vertex yang tidak dapat dilewati — secara efektif menghapus vertex dari graph.

Dijkstra pada Grid: Aturan dan Mekanisme #

Aturan #

Dijkstra menjelajah graph dari source, mempertahankan jarak terpendek yang diketahui untuk setiap vertex. Pada setiap iterasi, ambil vertex dengan jarak terkecil yang belum diproses, lalu relax edge-edge tetangganya: bila jarak lewat vertex saat ini lebih kecil dari jarak yang tersimpan, update dan masukkan ke priority queue. Algoritma berhenti ketika target terproses atau queue kosong.

Mekanisme di Balik Layar #

Pada grid dengan bobot uniform, BFS sebenarnya sudah optimal dan lebih sederhana. Tetapi Dijkstra adalah generalisasi yang menangani bobot non-uniform (mis. medan rawa butuh biaya 5, jalan beraspal biaya 1). Pemilihan priority queue dengan comparator greater<State> mengubah max-heap default menjadi min-heap — vertex dengan dist terkecil keluar lebih dulu.

Untuk rekonstruksi jalur, kita simpan parent[r][c] selama relaxation. Setelah target tercapai, telusuri parent mundur dari target ke source, lalu reverse.

Kompleksitas #

Untuk grid n × m: V = n × m, E ≈ 4V, total O(V log V). Pada grid 1000×1000, ini sekitar 10⁶ operasi — masih dalam batas 1 detik.

Kode: Dijkstra pada Grid dengan Rintangan #

#include <iostream>
#include <vector>
#include <queue>
#include <string>
#include <algorithm>
using namespace std;

const int INF = 1e9;
int dr[] = {-1, 1, 0, 0};
int dc[] = {0, 0, -1, 1};
const char* DIR_NAME[] = {"atas", "bawah", "kiri", "kanan"};

struct State {
    int r, c, dist;
    bool operator>(const State& o) const { return dist > o.dist; }
};

vector<pair<int,int>> dijkstraGrid(const vector<string>& grid,
                                   int sr, int sc, int tr, int tc) {
    int rows = grid.size();
    int cols = grid[0].size();
    vector<vector<int>> dist(rows, vector<int>(cols, INF));
    vector<vector<pair<int,int>>> parent(rows,
        vector<pair<int,int>>(cols, {-1,-1}));

    priority_queue<State, vector<State>, greater<State>> pq;
    dist[sr][sc] = 0;
    pq.push({sr, sc, 0});

    while (!pq.empty()) {
        State cur = pq.top(); pq.pop();
        if (cur.r == tr && cur.c == tc) break;
        if (cur.dist > dist[cur.r][cur.c]) continue;

        for (int d = 0; d < 4; ++d) {
            int nr = cur.r + dr[d];
            int nc = cur.c + dc[d];
            if (nr < 0 || nr >= rows || nc < 0 || nc >= cols) continue;
            if (grid[nr][nc] == '#') continue;  // rintangan

            int nd = cur.dist + 1;
            if (nd < dist[nr][nc]) {
                dist[nr][nc] = nd;
                parent[nr][nc] = {cur.r, cur.c};
                pq.push({nr, nc, nd});
            }
        }
    }

    // Reconstruct path
    vector<pair<int,int>> path;
    if (dist[tr][tc] == INF) return path;  // tidak tercapai
    for (pair<int,int> cur = {tr, tc}; cur != make_pair(-1,-1);
         cur = parent[cur.first][cur.second]) {
        path.push_back(cur);
    }
    reverse(path.begin(), path.end());
    return path;
}

int main() {
    // '#' = rintangan, '.' = jalan, 'S' = start, 'T' = target
    vector<string> grid = {
        "S....",
        ".###.",
        "..#..",
        ".#.#.",
        "....T"
    };

    int sr = 0, sc = 0, tr = 4, tc = 4;

    cout << "=== Pencarian Jalur (Dijkstra pada Grid) ===\n\n";
    cout << "Peta (S=start, T=target, #=rintangan):\n";
    for (const auto& row : grid) cout << "  " << row << "\n";
    cout << "\n";

    auto path = dijkstraGrid(grid, sr, sc, tr, tc);

    if (path.empty()) {
        cout << "Tidak ada jalur dari S ke T.\n";
        return 0;
    }

    // Visualisasi jalur pada grid
    vector<string> viz = grid;
    for (size_t i = 1; i + 1 < path.size(); ++i) {
        viz[path[i].first][path[i].second] = '*';
    }

    cout << "Jalur terpendek (panjang=" << path.size()-1 << "):\n";
    for (const auto& row : viz) cout << "  " << row << "\n";
    cout << "\nUrutan koordinat jalur:\n";
    for (size_t i = 0; i < path.size(); ++i) {
        cout << "  [" << i << "] (" << path[i].first
             << "," << path[i].second << ")";
        if (i > 0) {
            int dr2 = path[i].first - path[i-1].first;
            int dc2 = path[i].second - path[i-1].second;
            for (int d = 0; d < 4; ++d) {
                if (dr[d] == dr2 && dc[d] == dc2) {
                    cout << "  -> " << DIR_NAME[d];
                    break;
                }
            }
        }
        cout << "\n";
    }
    return 0;
}

Output yang Dihasilkan:

=== Pencarian Jalur (Dijkstra pada Grid) ===

Peta (S=start, T=target, #=rintangan):
  S....
  .###.
  ..#..
  .#.#.
  ....T

Jalur terpendek (panjang=8):
  S****
  .###*
  ..#.*
  .#.#*
  ....T

Urutan koordinat jalur:
  [0] (0,0)
  [1] (0,1)  -> kanan
  [2] (0,2)  -> kanan
  [3] (0,3)  -> kanan
  [4] (0,4)  -> kanan
  [5] (1,4)  -> bawah
  [6] (2,4)  -> bawah
  [7] (3,4)  -> bawah
  [8] (4,4)  -> bawah

Bedah Kode Baris-per-Baris #

1. int dr[] = {-1, 1, 0, 0}; int dc[] = {0, 0, -1, 1};: array perpindahan baris/kolom untuk empat arah ortogonal. Konvensi: indeks 0=atas, 1=bawah, 2=kiri, 3=kanan. Loop for (int d = 0; d < 4; ++d) menerapkan keempat arah.
2. struct State { int r, c, dist; bool operator>(const State& o) const { return dist > o.dist; } };: state pada priority queue. Operator > mengubah max-heap default menjadi min-heap — priority_queue<State, vector<State>, greater<State>> mengeluarkan State dengan dist terkecil lebih dulu.
3. vector<vector<int>> dist(rows, vector<int>(cols, INF));: matriks jarak. Inisialisasi INF menyatakan “belum dikunjungi”. Update terjadi saat relaxation.
4. vector<vector<pair<int,int>>> parent(...): matriks parent untuk rekonstruksi jalur. parent[r][c] menyimpan koordinat predecessor terbaik.
5. if (cur.dist > dist[cur.r][cur.c]) continue;: skip stale entry. Priority queue bisa berisi banyak entry untuk sel yang sama dengan dist berbeda; skip entry yang sudah tidak relevan mencegah pemrosesan ulang.
6. if (grid[nr][nc] == '#') continue;: lewati rintangan. Secara efektif, rintangan dianggap vertex yang tidak memiliki edge masuk.
7. if (nd < dist[nr][nc]) { dist[nr][nc] = nd; parent[nr][nc] = {cur.r, cur.c}; pq.push({nr, nc, nd}); }: relaxation. Update jarak, simpan parent, push state baru ke queue.
8. for (pair<int,int> cur = {tr, tc}; cur != make_pair(-1,-1); cur = parent[cur.first][cur.second]): telusuri jalur mundur dari target ke source. Loop berhenti ketika parent {-1,-1} (yaitu source yang parent-nya tidak pernah di-set).
9. reverse(path.begin(), path.end());: urutan dari target ke source dibalik menjadi source ke target — siap untuk ditampilkan atau dieksekusi sebagai urutan gerakan.

A*: Mempercepat dengan Heuristik #

Dijkstra menjelajah ke segala arah secara seragam. A* menambahkan heuristik admissible — estimasi biaya ke target — untuk memandu pencarian ke arah yang menjanjikan. Pada grid, heuristik yang umum adalah Manhattan distance: h(r,c) = |r-tr| + |c-tc|.

Aplikasi Nyata #

Ringkasan #

• Grid 2D adalah graph implisit: setiap sel adalah vertex, tetangga ortogonal adalah edge.
• Dijkstra pada grid uniform setara dengan BFS tetapi mendukung bobot berbeda.
• Rekonstruksi jalur dilakukan dengan matriks parent yang dilacak mundur dari target.
• Skip stale entry (if (cur.dist > dist[...]) continue;) mencegah pemrosesan duplikat.
• A* mempercepat Dijkstra dengan heuristik admissible (Manhattan untuk grid 4-arah).
• Untuk bobot uniform murni, BFS lebih sederhana dan lebih cepat.