Chương trình C++ tìm đường đi ngắn nhất từ một nguồn (SSSP) trong DAG

Đây là chương trình C++ tìm SSSP (Single Source Shortest Path) trong DAG (Directed Acyclic Graphs) sử dụng thuật toán Dijkstra để tìm từ nút đầu tiên đến mọi nút khác với độ dài đường đi ngắn nhất hiển thị bên cạnh mỗi cặp đỉnh.

Thuật toán

Bắt đầu
  Nhập các phần tử của đồ thị.
  hàm shortestpath():
    Khởi tạo biến
    a[i] = 1
    d[i] = 0
    s[i].from = 0
    Vòng lặp i = 0 đến 3
      nếu b[0][i] == 0 tiếp tục
      ngược lại d[i] = b[0][i], s[i].from = 0
    Vòng lặp while (c < 4)
      khởi tạo min = INFINITY
      với i = 0 đến 3
        nếu min <= d[i] hoặc d[i] == 0 hoặc a[i] == 1 thì tiếp tục
        ngược lại nếu min > d[i] thì min = d[i]
      với k = 0 đến 3
        nếu min == d[k] thì t = k, break
        ngược lại tiếp tục
      a[t] = 1
      với j = 0 đến 3
        nếu a[j] == 1 hoặc b[t][j] == 0 thì tiếp tục
        ngược lại nếu a[j] != 1
          nếu d[j] > (d[t] + b[t][j]) thì d[j] = d[t] + b[t][j], s[i].from = t
      tăng c
    Với i = 0 đến 3
      In chi phí nhỏ nhất từ node1 đến node2.
Kết thúc

Ví dụ mã nguồn

#include <iostream>
using namespace std;

#define INFINITY 9999

struct node {
    int from;
} s[4];

int c = 0;

void djikstras(int *a, int b[][4], int *d) {
    int i = 0, j, min, t;
    a[i] = 1;
    d[i] = 0;
    s[i].from = 0;
    for (i = 0; i < 4; i++) {
        if (b[0][i] == 0) continue;
        else {
            d[i] = b[0][i];
            s[i].from = 0;
        }
    }
    while (c < 4) {
        min = INFINITY;
        for (i = 0; i < 4; i++) {
            if (min <= d[i] || d[i] == 0 || a[i] == 1) continue;
            else if (min > d[i]) min = d[i];
        }
        for (int k = 0; k < 4; k++) {
            if (min == d[k]) {
                t = k;
                break;
            } else continue;
        }
        a[t] = 1;
        for (j = 0; j < 4; j++) {
            if (a[j] == 1 || b[t][j] == 0) continue;
            else if (a[j] != 1) {
                if (d[j] > (d[t] + b[t][j])) {
                    d[j] = d[t] + b[t][j];
                    s[i].from = t;
                }
            }
        }
        c++;
    }
    for (int i = 0; i < 4; i++) {
        cout << "from node " << s[i].from << " cost is: " << d[i] << endl;
    }
}

int main() {
    int a[4];
    int d[4];
    for (int k = 0; k < 4; k++) d[k] = INFINITY;
    for (int i = 0; i < 4; i++) a[i] = 0;
    int b[4][4];
    for (int i = 0; i < 4; i++) {
        cout << "nhập giá trị cho hàng " << (i+1) << endl;
        for (int j = 0; j < 4; j++) cin >> b[i][j];
    }
    djikstras(a, b, d);
}

Kết quả

nhập giá trị cho hàng 1
0 1 3 2
nhập giá trị cho hàng 2
2 1 3 0
nhập giá trị cho hàng 3
2 3 0 1
nhập giá trị cho hàng 4
1 3 2 0
from node 0 cost is: 0
from node 0 cost is: 1
from node 0 cost is: 3
from node 0 cost is: 2