전기 회로에서 Wire Length를 최적화하기 위한 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, Find shortest path for all components. A) Pick the minimum distance component from the set of components not yet processed. B) Mark the picked component as processed. C) Update dist value of the adjacent components of the picked component. D) Update dist[v] only if is not in sptSet, there is an edge from u to v, and total weight of path from src to v through u is smaller than current value of 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;
//Find shortest path for all components.
for (int cnt = 0; cnt < N - 1; cnt++) {
//Pick the minimum distance component from the set of
//components not yet processed.
int u = minDist(dist, sptSet);
//Mark the picked component as processed.
sptSet[u] = true;
//Update dist value of the adjacent components of the picked component.
for (int v = 0; v < N; v++)
if (!sptSet[v] && g[u][v] && dist[u] != INT_MAX && dist[u] + g[u][v] < dist[v])
//Update dist[v] only if is not in sptSet, there is an edge from
//u to v, and total weight of path from src to v through u is
//smaller than current value of 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