資料結構
網路
關係資料庫管理系統 (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 次瀏覽
廣告