기차를 사용하여 목적지에 도달하는 최소 비용 찾기

이 문제의 경우 여정에 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