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 trạm trên một hành trình. Xe bắt đầu hành trình từ trạm 0 đến N-1. Trong một bảng, giá vé cho tất cả các cặp trạm được cho. Ta phải tìm chi phí tối thiểu để đến đích với những chi phí cho trước.

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

Đầu vào: Ma trận chi phí của hành trình.
0  15  80  90
∞   0  40  50
∞  ∞   0  70
∞  ∞  ∞   0
Đầu ra: Chi phí tối thiểu là 65.
Trước tiên đi đến trạm 1 từ 0 (chi phí 15), sau đó 1 đến 4 (chi phí 50). Tổng chi phí 65.

Thuật toán

findMinCost(cost)
Đầu vào: Ma trận chi phí từ mỗi nguồn đến mỗi đích.
Đầu ra: Tìm chi phí tối thiểu để đến đích.
Bắt đầu
  định nghĩa mảng costLoc, kích thước bằng số lượng địa điểm,
  điền costLoc với ∞.
  n := số lượng địa điểm
  costLoc[0] := 0
  với mỗi nguồn i đến mỗi đích j, thực hiện
    nếu costLoc[j] > costLoc[i] + cost[i, j] thì
      costLoc[j] := costLoc[i] + cost[i, j]
    kết thúc
  kết thúc
  trả về costLoc[n-1]
Kết thúc

Ví dụ (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() {
  // tìm chi phí nhỏ nhất có thể để đến đích
  int costStation[NODE]; // lưu chi phí để đến bất kỳ trạm nào từ 0
  for (int i = 0; i < NODE; i++)
    costStation[i] = INF; // ban đầu tất cả là vô cực
  costStation[0] = 0; // chi phí cho trạm 0 là 0 vì là điểm bắt đầu
  
  for (int i = 0; i < NODE; i++)
    for (int j = i+1; j < NODE; j++)
      if (costStation[j] > costStation[i] + cost[i][j])
        // tìm trạm trung gian cho chi phí tối thiểu
        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