โปรแกรม C++ เพื่อเพิ่มประสิทธิภาพความยาวสายไฟในวงจรไฟฟ้า

นี่คือโปรแกรม C++ สำหรับเพิ่มประสิทธิภาพความยาวสายไฟในวงจรไฟฟ้า โดยใช้อัลกอริทึม Dijkstra เพื่อหาเส้นทางสั้นที่สุด

อัลกอริทึม

Begin
  Function optimizeLength():
    1) ประกาศอาเรย์ dist[N]
    2) sptSet[i] จะเป็น true หากคอมโพเนนต์ i ถูกรวมในต้นไม้เส้นทางสั้นที่สุด
    3) เริ่มต้นระยะทางทั้งหมดเป็น INFINITE และ stpSet[] เป็น false
    4) ระยะทางของคอมโพเนนต์ต้นทางจากตัวมันเองจะเป็น 0 เสมอ
    5) วนลูป for cnt = 0 ถึง N-2 หาเส้นทางสั้นที่สุดสำหรับทุกคอมโพเนนต์
       A) เลือกคอมโพเนนต์ที่มีระยะทางน้อยที่สุดจากเซตที่ยังไม่ได้ประมวลผล
       B) ทำเครื่องหมายคอมโพเนนต์ที่เลือกว่าได้รับการประมวลผลแล้ว
       C) อัปเดตค่า dist ของคอมโพเนนต์ที่อยู่ติดกับคอมโพเนนต์ที่เลือก
       D) อัปเดต dist[v] ก็ต่อเมื่อไม่อยู่ใน sptSet มีขอบจาก u ไป v และน้ำหนักรวมของเส้นทางจาก src ไป v ผ่าน u น้อยกว่าค่า dist[v] ปัจจุบัน
End

ตัวอย่างโค้ด

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

int minDist(int dist[], bool sptSet[]) {
  // หาคอมโพเนนต์ที่มีค่าระยะทางน้อยที่สุด
  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) {
  // แสดงผลลัพธ์
  cout << "Component\tDistance from other component\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) {
  // ทำงาน optimizeLength() function
  int dist[N];
  bool sptSet[N];
  for (int i = 0; i < N; i++)
    dist[i] = INT_MAX, sptSet[i] = false;
  dist[src] = 0;
  // หาเส้นทางสั้นที่สุดสำหรับทุกคอมโพเนนต์
  for (int cnt = 0; cnt < N - 1; cnt++) {
    // เลือกคอมโพเนนต์ที่มีระยะทางน้อยที่สุด
    int u = minDist(dist, sptSet);
    // ทำเครื่องหมายคอมโพเนนต์ที่เลือก
    sptSet[u] = true;
    // อัปเดตค่า dist ของคอมโพเนนต์ที่อยู่ติดกัน
    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 << "Enter the starting component: ";
  int s;
  cin >> s;
  optimizeLength(g, s);
  return 0;
}

ผลลัพธ์

Enter the starting component: 4
Component Distance from other component
0 5
1 1
2 9
3 11
4 0
5 3