ন্যূনতম খরচের পথ

বিভিন্ন খরচের একটি ম্যাট্রিক্স দেওয়া হয়েছে৷ এছাড়াও, গন্তব্য সেল প্রদান করা হয়. স্টার্টিং সেল (0, 0) থেকে গন্তব্য সেলে পৌঁছানোর জন্য আমাদের ন্যূনতম খরচের পথ খুঁজে বের করতে হবে।

ম্যাট্রিক্সের প্রতিটি কক্ষ সেই কক্ষের মধ্য দিয়ে অতিক্রম করার খরচ উপস্থাপন করে।

একটি কোষ থেকে, আমরা কোথাও যেতে পারি না, আমরা গন্তব্যে পৌঁছানোর জন্য ডানে বা নীচে বা নীচের ডানদিকের কর্ণ কোষে যেতে পারি।

ইনপুট এবং আউটপুট

Input:
The cost matrix. And the destination point. In this case the destination point is (2, 2).
1 2 3
4 8 2
1 5 3

Output:
The minimum cost to reach to the destination from (0, 0). The minimum cost is 8.

অ্যালগরিদম

minCostPath(destX, destY, cost)

ইনপুট - গন্তব্যের (x, y) স্থান এবং খরচ ম্যাট্রিক্স।

আউটপুট - গন্তব্যে পৌঁছাতে ন্যূনতম খরচ।

Begin
   define matrix totalCost, whose order is same as cost matrix
   totalCost[0, 0] = cost[0, 0]

   for i := 1 to destX, do
      totalCost[i, 0] := totalCost[i-1, 0] + cost[i, 0]
   done

   for j := 1 to destY, do
      totalCost[0, j] := totalCost[0, j-1] + cost[0, j]
   done

   for all places (i, j) from (1, 1) to (destX, destY), do
      totalCost[i, j] := minimum of totalCost[i-1, j-1], totalCost[i-1, j] and (totalCost[i, j-1] + cost[i,j])
   done

   return totalCost[destX, destY]
End

উদাহরণ

#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];    //set first col of totalCost array

   for (int j = 1; j <= destY; j++)            //set first row of totalCost array
      totalCost[0][j] = totalCost[0][j-1] + cost[0][j];

   for (int i = 1; i <= destX; i++)            //for second row and column to all
      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);    //destination (2, 2)
   return 0;
}

আউটপুট

Minimum Cost: 8