C ++程序可优化电路中的电线长度

  • Z时代
  • 2024-01-10
  • 分类：综合

这是一个用于优化电路中电线长度的C ++程序。

算法

Begin
   Function optimizeLength() :
   1) Declare a array dist[N].
   2) sptSet[i] will be true if component i is included in shortest
   path tree or shortest distance from src to i is finalized.
   3) Initialize all distances as INFINITE and stpSet[] as false
   4) Distance of source component from itself will be always 0.
   5) Run a for loop cnt = 0 to N-2, 查找所有组件的最短路径。
      A) 的集合中选择最小距离分量 组件尚未处理。
      B) 将选择的组件标记为已处理。
      C) 更新选取的组件的相邻组件的dist值。
      D) 有一个边
      u到v，从src到通过u的v的路径总权重为 小于dist [v]的当前值。
End

示例

#include <limits.h>
#include <iostream>
using namespace std;
#define N 6
int minDist(int dist[], bool sptSet[]) { //to find component with minimum distance value.
   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) { // display the solution.
   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) { //perform 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])
      //有一个边
      //u到v，从src到通过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

以上是 C ++程序可优化电路中的电线长度 的全部内容， 来源链接： utcz.com/z/322041.html

回到顶部