यह एक C++ प्रोग्राम है जो इलेक्ट्रिकल सर्किट में वायर लंबाई को ऑप्टिमाइज़ करता है।
एल्गोरिदम
Begin Function optimizeLength() : 1) एक ऐरे dist[N] डिक्लेयर करें। 2) sptSet[i] सच होगा यदि कंपोनेंट i शॉर्टेस्ट पाथ ट्री में शामिल है या src से i की शॉर्टेस्ट दूरी फाइनलाइज़ हो गई है। 3) सभी दूरियों को INFINITE और stpSet[] को फॉल्स इनिशियलाइज़ करें। 4) सोर्स कंपोनेंट की स्वयं से दूरी हमेशा 0 होगी। 5) cnt = 0 से N-2 तक फॉर लूप चलाएं, सभी कंपोनेंट्स के लिए शॉर्टेस्ट पाथ खोजें। A) अभी तक प्रोसेस न किए गए कंपोनेंट्स के सेट से न्यूनतम दूरी वाला कंपोनेंट चुनें। B) चुने गए कंपोनेंट को प्रोसेस्ड मार्क करें। C) चुने गए कंपोनेंट के आसन्न कंपोनेंट्स के dist वैल्यू को अपडेट करें। D) dist[v] को केवल तभी अपडेट करें यदि यह sptSet में नहीं है, u से v तक एक एज है, और src से v तक u के माध्यम से पाथ का कुल वजन dist[v] के वर्तमान मान से छोटा है। End
उदाहरण
#include <limits.h> #include <iostream> using namespace std; #define N 6 int minDist(int dist[], bool sptSet[]) { //न्यूनतम दूरी मान वाला कंपोनेंट खोजने के लिए। 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) { // समाधान प्रदर्शित करें। 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) { //optimizeLength() फंक्शन निष्पादित करें int dist[N]; bool sptSet[N]; for (int i = 0; i < N; i++) dist[i] = INT_MAX, sptSet[i] = false; dist[src] = 0; //सभी कंपोनेंट्स के लिए शॉर्टेस्ट पाथ खोजें। for (int cnt = 0; cnt < N - 1; cnt++) { //अभी तक प्रोसेस न किए गए कंपोनेंट्स के सेट से न्यूनतम दूरी वाला कंपोनेंट चुनें। int u = minDist(dist, sptSet); //चुने गए कंपोनेंट को प्रोसेस्ड मार्क करें। sptSet[u] = true; //चुने गए कंपोनेंट के आसन्न कंपोनेंट्स के dist वैल्यू को अपडेट करें। for (int v = 0; v < N; v++) if (!sptSet[v] && g[u][v] && dist[u] != INT_MAX && dist[u] + g[u][v] < dist[v]) //dist[v] को केवल तभी अपडेट करें यदि यह sptSet में नहीं है, u से v तक एक एज है, और src से v तक u के माध्यम से पाथ का कुल वजन 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