Chương trình C++ tối ưu hóa độ dài dây dẫn trong mạch điện

Đây là chương trình C++ để tối ưu hóa độ dài dây dẫn trong mạch điện. Chương trình sử dụng thuật toán Dijkstra để tìm đường đi ngắn nhất từ một thành phần nguồn đến các thành phần khác trong đồ thị biểu diễn mạch điện.

Thuật toán

Bắt đầu
  Hàm optimizeLength():
    1) Khai báo mảng dist[N].
    2) sptSet[i] = true nếu thành phần i đã được đưa vào cây đường đi ngắn nhất
       hoặc khoảng cách ngắn nhất từ nguồn đến i đã được xác định.
    3) Khởi tạo tất cả khoảng cách = VÔ CỰC và sptSet[] = false.
    4) Khoảng cách từ nguồn đến chính nó luôn = 0.
    5) Vòng lặp cnt = 0 đến N-2, tìm đường đi ngắn nhất cho tất cả thành phần.
       A) Chọn thành phần có khoảng cách nhỏ nhất từ tập chưa xử lý.
       B) Đánh dấu thành phần đã chọn là đã xử lý.
       C) Cập nhật giá trị dist của các thành phần kề với thành phần đã chọn.
       D) Cập nhật dist[v] chỉ nếu v chưa trong sptSet, có cạnh từ u đến v,
          và tổng trọng số đường đi từ nguồn đến v qua u nhỏ hơn dist[v] hiện tại.
Kết thúc

Ví dụ mã nguồn

#include <limits.h>
#include <iostream>
using namespace std;
#define N 6

int minDist(int dist[], bool sptSet[]) {
    // tìm thành phần có giá trị khoảng cách nhỏ nhất
    int min = INT_MAX, min_index;
    for (int v = 0; v < N; v++)
        if (sptSet[v] == false && dist[v] <= min)
            min = dist[v], min_index = v;
    return min_index;
}

void displaySolution(int dist[], int n) {
    // hiển thị kết quả
    cout << "Thành phần\tKhoảng cách từ thành phần khác\n";
    for (int i = 0; i < n; i++)
        printf("%d\t\t%d\n", i, dist[i]);
}

void optimizeLength(int g[N][N], int src) {
    int dist[N];
    bool sptSet[N];
    for (int i = 0; i < N; i++)
        dist[i] = INT_MAX, sptSet[i] = false;
    dist[src] = 0;
    // Tìm đường đi ngắn nhất cho tất cả thành phần
    for (int cnt = 0; cnt < N - 1; cnt++) {
        // Chọn thành phần khoảng cách nhỏ nhất chưa xử lý
        int u = minDist(dist, sptSet);
        // Đánh dấu đã xử lý
        sptSet[u] = true;
        // Cập nhật khoảng cách các thành phần kề
        for (int v = 0; v < N; v++)
            if (!sptSet[v] && g[u][v] && dist[u] != INT_MAX &&
                dist[u] + g[u][v] < dist[v])
                dist[v] = dist[u] + g[u][v];
    }
    displaySolution(dist, N);
}

int main() {
    int g[N][N] = { { 0, 0, 6, 7, 0, 4},
                    { 4, 0, 8, 0, 1, 2 },
                    { 0, 9, 0, 2, 0, 4 },
                    { 0, 0, 7, 0, 9, 5 },
                    { 0, 1, 0, 0, 6, 7 },
                    { 6, 7, 0, 0, 2, 3} };
    cout << "Nhập thành phần bắt đầu: ";
    int s;
    cin >> s;
    optimizeLength(g, s);
    return 0;
}

Kết quả

Nhập thành phần bắt đầu: 4
Thành phần    Khoảng cách từ thành phần khác
0             5
1             1
2             9
3             11
4             0
5             3