C ++程序可优化电路中的电线长度
这是一个用于优化电路中电线长度的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