ট্রেন ব্যবহার করে গন্তব্যে পৌঁছানোর সর্বনিম্ন খরচ খুঁজুন

এই সমস্যার জন্য, যাত্রায় N স্টপ আছে৷ গাড়িটি স্টপ 0 থেকে N-1 পর্যন্ত যাত্রা শুরু করে। একটি টেবিলে, সমস্ত জোড়া স্টেশনের টিকিটের মূল্য দেওয়া আছে। আমাদের সেই প্রদত্ত খরচ দিয়ে গন্তব্যে পৌঁছানোর জন্য সর্বনিম্ন খরচ খুঁজে বের করতে হবে।

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

Input:
The cost matrix of the journey.
0 15 80 90
∞  0 40 50
∞  ∞  0 70
∞  ∞  ∞  0

Output:
The minimum cost is 65.
At first go to the destination 1 from 0. (cost 15), then 1 to 4 (cost 50). So total cost 65.

অ্যালগরিদম

findMinCost(cost)

ইনপুট - প্রতিটি উৎস থেকে প্রতিটি গন্তব্যে খরচ ম্যাট্রিক্স।

আউটপুট - একটি গন্তব্যে পৌঁছানোর সর্বনিম্ন খরচ খুঁজুন।

Begin
   define array costLoc, whose size is same as sumber of locations,
   fill costLoc with ∞.
   n := number of locations
   costLoc[0] := 0

   for each source i to each destination j, do
      if costLoc[j] > costLoc[i] + cost[i, j], then
         costLoc[j] := costLoc[i] + cost[i, j]
   done

   return costLoc[n-1]
End

উদাহরণ

#include<iostream>
#define INF INT_MAX
#define NODE 4
using namespace std;

int cost[NODE][NODE] = {
   {0, 15, 80, 90},
   {INF, 0, 40, 50},
   {INF, INF, 0, 70},
   {INF, INF, INF, 0}
};

int findMinCost() {          //find smallest possible cost to reach destination
   int costStation[NODE];    //store cost to reach any station from 0

   for (int i=0; i<NODE; i++)
      costStation[i] = INF;       //initially all are infinity
   costStation[0] = 0;         //cost for station 0 is 0 as it is starting point

   for (int i=0; i<NODE; i++)
      for (int j=i+1; j<NODE; j++)
         if (costStation[j] > costStation[i] + cost[i][j])    //find intermediate station for min cost costStation[j] = costStation[i] + cost[i][j];
   return costStation[NODE-1];
}

int main() {
   cout << "The Minimum cost to reach station " << NODE << " is " << findMinCost() << endl;
   return 0;
}

আউটপুট

The Minimum cost to reach station 4 is 65