Dijkstra pada Bagian 2 menghasilkan array dist berisi jarak terpendek dari start ke setiap sel. Tetapi dist saja tidak memberitahu jalur mana yang ditempuh — hanya panjangnya. Untuk menampilkan jalur, kita perlu menyimpan parent setiap sel: sel mana yang menjadi pendahulu pada jalur terpendek. Pada bagian ini kita memperluas Dijkstra untuk mengisi array parent, lalu melakukan backtrack dari goal ke start untuk merekonstruksi jalur.

Menyimpan Parent saat Relaksasi #

Setiap kali dist[nb] diperbarui melalui relaksasi dari u, kita catat parent[nb] = u. Dengan demikian, jalur dapat ditelusuri mundur dari goal ke start.

cpp 
std::vector<std::vector<Cell>> parent(g.rows,
    std::vector<Cell>(g.cols, {-1, -1}));

// Dalam loop relaksasi:
if (nd < dist[nb.row][nb.col]) {
    dist[nb.row][nb.col] = nd;
    parent[nb.row][nb.col] = u;   // catat predecessor
    pq.push({nd, nb});
}

Backtrack dari Goal ke Start #

Untuk merekonstruksi jalur:

  1. Mulai dari goal.
  2. Selama sel saat ini bukan start, ambil parent sel tersebut, masukkan ke list.
  3. Balik list agar urutan dari start ke goal.
cpp 
std::vector<Cell> reconstructPath(
        const std::vector<std::vector<Cell>>& parent,
        const Cell& start, const Cell& goal) {
    std::vector<Cell> path;
    Cell cur = goal;
    while (!(cur == start)) {
        path.push_back(cur);
        cur = parent[cur.row][cur.col];
        if (cur.row == -1) return {};   // tidak ada jalur
    }
    path.push_back(start);
    std::reverse(path.begin(), path.end());
    return path;
}

Program Lengkap Bagian 3 #

cpp 
#include <algorithm>
#include <iomanip>
#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<Cell>>& parent) {
    std::vector<std::vector<int>> dist(g.rows, std::vector<int>(g.cols, INF));
    parent.assign(g.rows, std::vector<Cell>(g.cols, {-1, -1}));
    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;
        for (const auto& nb : neighbors(g, u)) {
            int nd = d + 1;
            if (nd < dist[nb.row][nb.col]) {
                dist[nb.row][nb.col] = nd;
                parent[nb.row][nb.col] = u;
                pq.push({nd, nb});
            }
        }
    }
    return dist;
}

std::vector<Cell> reconstructPath(
        const std::vector<std::vector<Cell>>& parent,
        const Cell& start, const Cell& goal) {
    std::vector<Cell> path;
    Cell cur = goal;
    while (!(cur == start)) {
        path.push_back(cur);
        cur = parent[cur.row][cur.col];
        if (cur.row == -1) return {};
    }
    path.push_back(start);
    std::reverse(path.begin(), path.end());
    return path;
}

void printPath(const Grid& g, const std::vector<Cell>& path) {
    if (path.empty()) {
        std::cout << "Tidak ada jalur dari start ke goal.\n";
        return;
    }
    std::vector<std::string> output = g.cells;
    for (size_t i = 1; i + 1 < path.size(); ++i) {
        const auto& c = path[i];
        output[c.row][c.col] = '*';
    }
    std::cout << "Jalur terpendek (panjang=" << path.size() - 1 << "):\n";
    for (const auto& row : output) std::cout << "  " << row << "\n";
}

int main() {
    Grid g({
        ".....",
        ".###.",
        ".S.#.",
        "...#.",
        "...G."
    });
    Cell start = {2, 1}, goal = {4, 3};
    std::vector<std::vector<Cell>> parent;
    dijkstra(g, start, parent);
    auto path = reconstructPath(parent, start, goal);
    printPath(g, path);
    return 0;
}

Output yang Dihasilkan:

text 
Jalur terpendek (panjang=4):
  .....
  .###.
  .S*#.
  ..*#.
  ..*G.

Jalur yang dipilih: (2,1) → (2,2) → (3,2) → (4,2) → (4,3). Start (2,1) dan goal (4,3) tetap ditampilkan sebagai S dan G; sel perantara ditandai *. Banyak jalur lain juga berpanjang 4 — algoritma Dijkstra memilih satu berdasarkan urutan neighbor yang diproses.

Bedah Baris Penting #

  1. parent.assign(g.rows, std::vector<Cell>(g.cols, {-1, -1})): inisialisasi parent dengan sel (-1, -1) sebagai penanda “belum memiliki predecessor”. Nilai ini menjadi guard saat backtrack — bila menemui (-1, -1) sebelum mencapai start, berarti tidak ada jalur.
  2. parent[nb.row][nb.col] = u: setiap kali dist[nb] diperbarui, parent juga diperbarui. Karena Dijkstra hanya memperbarui dist bila ditemukan jarak lebih baik, parent selalu menyimpan predecessor pada jalur terpendek.
  3. while (!(cur == start)): loop mundur dari goal ke start. Pemakaian !(a == b) alih-alih a != b menjamin kompatibel dengan struct yang hanya mendefinisikan operator==.
  4. if (cur.row == -1) return {}: guard untuk kasus tidak ada jalur. Bila goal tidak terjangkau, parent tidak pernah diisi sehingga backtrack menemui (-1, -1) seketika.
  5. for (size_t i = 1; i + 1 < path.size(); ++i): kita tandai sel selain start dan goal dengan *. Start (S) dan goal (G) tetap dalam bentuk aslinya agar posisi awal dan akhir jelas terbaca.
  6. std::reverse(path.begin(), path.end()): backtrack menghasilkan urutan goal→start, kita balik menjadi start→goal. Tanpa reverse, jalur dicetak dari goal ke start — masih valid tetapi tidak intuitif untuk dibaca.

Kompilasi dan Pengujian #

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

Pada Bagian 4, kita menguji berbagai skenario untuk memastikan rekonstruksi jalur bekerja pada kasus edge.