หา Minimum Cost Path ใน Grid 4 ทิศทางด้วย Dijkstra ใน C++

โจทย์

กำหนด 2D array แต่ละเซลล์มีค่า cost หาเส้นทางจากมุมซ้ายบน (0,0) ไปมุมขวาล่าง (n-1,m-1) ที่มี cost รวมน้อยที่สุด สามารถเดินได้ 4 ทิศทาง (ซ้าย ขวา บน ล่าง)

วิธีการแก้ปัญหา

ใช้ Dijkstra's Algorithm บน Grid:

• โหนด = เซลล์ (x,y), edge weight = cost ของเซลล์ปลายทาง
• Priority queue (min-heap) เรียงตาม distance
• Distance array เก็บ min cost ถึงแต่ละเซลล์
• Relaxation: ถ้าพบเส้นทางสั้นกว่า → update distance และ push เข้า queue

ตัวอย่างโค้ด C++

#include <bits/stdc++.h>
using namespace std;
#define ROW 5
#define COL 5

class cell {
public:
    int x, y, distance;
    cell(int x, int y, int distance) : x(x), y(y), distance(distance) {}
};

bool operator<(const cell& a, const cell& b) {
    if (a.distance == b.distance) {
        if (a.x != b.x) return (a.x < b.x);
        else return (a.y < b.y);
    }
    return (a.distance < b.distance);
}

bool isOk(int i, int j) { return (i >= 0 && i < COL && j >= 0 && j < ROW); }

int solve(int grid[ROW][COL], int row, int col) {
    int matrix[row][col];
    for (int i = 0; i < row; i++)
        for (int j = 0; j < col; j++)
            matrix[i][j] = INT_MAX;
    int dx[] = {-1, 0, 1, 0};
    int dy[] = {0, 1, 0, -1};
    set<cell> st;
    st.insert(cell(0, 0, 0));
    matrix[0][0] = grid[0][0];
    while (!st.empty()) {
        cell k = *st.begin();
        st.erase(st.begin());
        for (int i = 0; i < 4; i++) {
            int x = k.x + dx[i];
            int y = k.y + dy[i];
            if (!isOk(x, y)) continue;
            if (matrix[x][y] > matrix[k.x][k.y] + grid[x][y]){
                if (matrix[x][y] != INT_MAX)
                    st.erase(st.find(cell(x, y, matrix[x][y])));
                matrix[x][y] = matrix[k.x][k.y] + grid[x][y];
                st.insert(cell(x, y, matrix[x][y]));
            }
        }
    }
    return matrix[row - 1][col - 1];
}

int main() {
    int grid[ROW][COL] = {
        {32, 101, 66, 13, 19},
        {11, 14, 48, 158, 7},
        {101, 114, 175, 12, 34},
        {89, 126, 42, 21, 141},
        {100, 33, 112, 42, 21}
    };
    cout << solve(grid, ROW, COL);
}

อินพุต

{32, 101, 66, 13, 19, 11, 14, 48, 158, 7, 101, 114, 175, 12, 34, 89, 126, 42, 21, 141, 100, 33, 112, 42, 21 };

เอาต์พุต

340