หาต้นทุนขั้นต่ำไปยังจุดหมายด้วยรถไฟ (Min Cost to Destination)

มี N สถานีในการเดินทาง เริ่มจากสถานี 0 ถึง N-1 กำหนดตารางค่าใช้จ่ายระหว่างทุกคู่สถานี ต้องการหาต้นทุนขั้นต่ำไปถึงปลายทาง

การรับค่าและแสดงผล

Input: เมทริกซ์ต้นทุน
0  15  80  90
INF 0  40  50
INF INF 0  70
INF INF INF 0

Output: The minimum cost is 65.
เส้นทาง: 0 → 1 (cost 15) → 3 (cost 50) = 65

อัลกอริทึม

findMinCost(cost) - Dynamic Programming แบบ Bottom-Up

Begin
  กำหนดอาร์เรย์ costLoc ขนาดเท่าจำนวนสถานี เติม INF
  n := จำนวนสถานี
  costLoc[0] := 0
  
  for ทุกต้นทาง i ไปทุกปลายทาง j do
    if costLoc[j] > costLoc[i] + cost[i,j] then
      costLoc[j] := costLoc[i] + cost[i,j]
    end if
  done
  
  return costLoc[n-1]
End

ตัวอย่างโค้ด (C++)

#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() {
  int costStation[NODE];
  for(int i = 0; i < NODE; i++) costStation[i] = INF;
  costStation[0] = 0;
  
  for(int i = 0; i < NODE; i++)
    for(int j = i+1; j < NODE; j++)
      if(costStation[j] > costStation[i] + cost[i][j])
        costStation[j] = costStation[i] + cost[i][j];
  
  return costStation[NODE-1];
}

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

ผลลัพธ์

The Minimum cost to reach station 4 is 65