न्यूनतम लागत पथ

विभिन्न लागत का एक मैट्रिक्स दिया गया है। साथ ही, गंतव्य सेल प्रदान किया गया है। हमें प्रारंभिक सेल (0, 0) से गंतव्य सेल तक पहुंचने के लिए न्यूनतम लागत पथ ढूंढना है।

मैट्रिक्स का प्रत्येक सेल उस सेल को पार करने की लागत दर्शाता है।

एक सेल से, हम कहीं भी नहीं जा सकते, हम गंतव्य तक पहुंचने के लिए केवल दाएं, नीचे या निचले-दाएं विकर्ण सेल में जा सकते हैं।

इनपुट और आउटपुट

इनपुट: कॉस्ट मैट्रिक्स। और गंतव्य बिंदु। इस मामले में गंतव्य बिंदु (2, 2) है।
1 2 3
4 8 2
1 5 3

आउटपुट: (0, 0) से गंतव्य तक पहुंचने की न्यूनतम लागत। न्यूनतम लागत 8 है।

एल्गोरिदम

minCostPath(destX, destY, cost)

इनपुट: गंतव्य का (x, y) स्थान, और कॉस्ट मैट्रिक्स
आउटपुट: गंतव्य तक पहुंचने की न्यूनतम लागत

शुरुआत
    totalCost मैट्रिक्स परिभाषित करें, जिसका ऑर्डर कॉस्ट मैट्रिक्स जैसा ही हो
    totalCost[0, 0] = cost[0, 0]
    i := 1 से destX तक, करें
        totalCost[i, 0] := totalCost[i-1, 0] + cost[i, 0]
    पूर्ण
    j := 1 से destY तक, करें
        totalCost[0, j] := totalCost[0, j-1] + cost[0, j]
    पूर्ण
    (1, 1) से (destX, destY) तक सभी स्थानों (i, j) के लिए, करें
        totalCost[i, j] := totalCost[i-1, j-1], totalCost[i-1, j] और (totalCost[i, j-1] + cost[i,j]) का न्यूनतम
    पूर्ण
    वापस totalCost[destX, destY]
अंत

उदाहरण (C++ कोड)

#include <iostream>
#define ROW 3
#define COL 3
using namespace std;

int cost[ROW][COL] = {
    {1, 2, 3},
    {4, 8, 2},
    {1, 5, 3}
};

int min(int a, int b, int c) {
    return (a < b) ? ((a < c) ? a : c) : ((b < c) ? b : c);
}

int minCostPath(int destX, int destY) {
    int totalCost[ROW][COL];
    totalCost[0][0] = cost[0][0];
    
    for (int i = 1; i <= destX; i++)
        totalCost[i][0] = totalCost[i-1][0] + cost[i][0];
    
    for (int j = 1; j <= destY; j++)
        totalCost[0][j] = totalCost[0][j-1] + cost[0][j];
    
    for (int i = 1; i <= destX; i++)
        for (int j = 1; j <= destY; j++)
            totalCost[i][j] = min(totalCost[i-1][j-1], totalCost[i-1][j], totalCost[i][j-1]) + cost[i][j];
    
    return totalCost[destX][destY];
}

int main() {
    cout << "Minimum Cost: " << minCostPath(2, 2);
    return 0;
}

आउटपुट

Minimum Cost: 8