数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法律研究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, 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
更新于：2019年7月30日
281 次浏览
广告