C Program to Optimize Wire Length in Electrical Circuit

«
»
This is a C Program to optimize wire length in electix circuit. This problem can be reduced to finding the shortest path between two components.

Here is source code of the C Program to Optimize Wire Length in Electrical Circuit. The C program is successfully compiled and run on a Linux system. The program output is also shown below.

  1. #include <stdio.h>
  2. #include <limits.h>
  3.  
  4. #define V 9
  5.  
  6. int minDistance(int dist[], int sptSet[]) {
  7.     int min = INT_MAX, min_index;
  8.     int v;
  9.     for (v = 0; v < V; v++)
  10.         if (sptSet[v] == 0 && dist[v] <= min)
  11.             min = dist[v], min_index = v;
  12.  
  13.     return min_index;
  14. }
  15.  
  16. int printSolution(int dist[], int n) {
  17.     printf("Vertex   Distance from Source\n");
  18.     int i;
  19.     for (i = 0; i < V; i++)
  20.         printf("%d \t\t %d\n", i, dist[i]);
  21. }
  22.  
  23. void shortestLength(int graph[V][V], int src) {
  24.     int dist[V];
  25.     int i, count;
  26.     int sptSet[V];
  27.  
  28.     for (i = 0; i < V; i++) {
  29.         dist[i] = INT_MAX;
  30.         sptSet[i] = 0;
  31.     }
  32.     dist[src] = 0;
  33.  
  34.     for (count = 0; count < V - 1; count++) {
  35.         int u = minDistance(dist, sptSet);
  36.  
  37.         sptSet[u] = 1;
  38.         int v;
  39.         for (v = 0; v < V; v++)
  40.  
  41.             if (!sptSet[v] && graph[u][v] && dist[u] != INT_MAX && dist[u]
  42.                     + graph[u][v] < dist[v])
  43.                 dist[v] = dist[u] + graph[u][v];
  44.     }
  45.  
  46.     printSolution(dist, V);
  47. }
  48.  
  49. int main() {
  50.     printf(
  51.             "An electric circuit can be represented as Graph where components are nodes and wires are edges between them.");
  52.     int graph[V][V] =
  53.             { { 0, 4, 0, 0, 0, 0, 0, 8, 0 }, 
  54.               { 4, 0, 8, 0, 0, 0, 0, 11, 0 }, 
  55.               { 0, 8, 0, 7, 0, 4, 0, 0, 2 },
  56.               { 0, 0, 7, 0, 9, 14, 0, 0, 0 }, 
  57.               { 0, 0, 0, 9, 0, 10, 0, 0, 0 }, 
  58.               { 0, 0, 4, 0, 10, 0, 2, 0, 0 }, 
  59.               { 0, 0, 0, 14, 0, 2, 0, 1, 6 }, 
  60.               { 8, 11, 0, 0, 0, 0, 1, 0, 7 }, 
  61.               { 0, 0, 2, 0, 0, 0, 6, 7, 0 } 
  62.             };
  63.     int c;
  64.     printf("Enter the component number from which you want to optimize wire lengths: ");
  65.     scanf("%d", &c);
  66.     printf("Optimized Lengths are: ");
  67.     shortestLength(graph, c);
  68.  
  69.     return 0;
  70. }

Output:

advertisement
$ gcc OptimizeWireLength.c
$ ./a.out
 
An electric circuit can be represented as Graph where components are nodes and wires are edges between them.
Enter the component number from which you want to optimize wire lengths: 3
Optimized Lengths are: 
Vertex   Distance from Source
0 		 19
1 		 15
2 		 7
3 		 0
4 		 9
5 		 11
6 		 13
7 		 14
8 		 9

Sanfoundry Global Education & Learning Series – 1000 C Programs.

Note: Join free Sanfoundry classes at Telegram or Youtube
advertisement
advertisement

Here’s the list of Best Books in C Programming, Data Structures and Algorithms.

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & technical discussions at Telegram SanfoundryClasses.