ट्रेन का उपयोग करके गंतव्य तक पहुंचने के लिए न्यूनतम लागत का पता लगाएं

इस समस्या के लिए, यात्रा पर N स्टॉप हैं। वाहन स्टॉप 0 से एन-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