電気回路のワイヤ長を最適化する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