Tìm chi phí tối thiểu để đến đích bằng tàu hỏa

Đối với bài toán này, có N điểm dừng trên một hành trình. Xe bắt đầu hành trình từ điểm dừng 0 đến điểm N-1. Trong một bảng, giá vé cho tất cả các cặp ga được đưa ra. Chúng ta phải tìm chi phí tối thiểu để đến đích với những chi phí đã cho đó.

Đầu vào và Đầu ra

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.

Thuật toán

findMinCost(cost)

Đầu vào - Ma trận chi phí từ mỗi nguồn đến mỗi điểm đến.

Đầu ra - Tìm chi phí tối thiểu để đến đích.

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

Ví dụ

#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;
}

Đầu ra

The Minimum cost to reach station 4 is 65