यहां हम दो वर्टेक्स के बीच सबसे छोटा पथ खोजने के लिए जॉनसन एल्गोरिदम देखेंगे।
ग्राफ यहां दिया गया है। एज के बीच सबसे छोटा पथ नीचे जैसा है। यह प्रोग्राम वर्टेक्स की संख्या, एज की संख्या, और उनकी लागत के साथ एज लेगा।
इनपुट - वर्टेक्स: 3
एज: 5
लागत के साथ एज -
1 2 8
2 1 12
1 3 22
3 1 6
2 3 4
आउटपुट - ग्राफ की दूरी मैट्रिक्स।
| 0 | 8 | 12 |
| 10 | 0 | 4 |
| 6 | 14 | 0 |
एल्गोरिदम
johnsonAlgorithm(cost)
इनपुट - दिए गए ग्राफ की लागत मैट्रिक्स।
आउटपुट - किसी भी वर्टेक्स से किसी भी वर्टेक्स के लिए सबसे छोटे पथ के लिए मैट्रिक्स।
Begin
'A' नामक एक और मैट्रिक्स बनाएं जो लागत मैट्रिक्स के समान हो, यदि iवीं पंक्ति और jवें स्तंभ के बीच कोई एज नहीं है, तो A[i,j] पर इन्फिनिटी रखें
for k := 1 to n, do
for i := 1 to n, do
for j := 1 to n, do
A[i, j] = A[i, j] और (A[i, k] + A[k, j]) का न्यूनतम
done
done
done
वर्तमान A मैट्रिक्स प्रदर्शित करें
End
उदाहरण
#include <iostream>
#define INF 9999
using namespace std;
int min(int a, int b);
int cost[10][10], adj[10][10];
inline int min(int a, int b) {
return (a < b) ? a : b;
}
int main() {
int vert, edge, i, j, k, c;
cout << "Enter no of vertices: ";
cin >> vert;
cout << "Enter no of edges: ";
cin >> edge;
cout << "Enter the EDGE Costs:\n";
for (k = 1; k <= edge; k++) { // इनपुट लें और इसे adj और cost मैट्रिक्स में स्टोर करें
cin >> i >> j >> c;
adj[i][j] = cost[i][j] = c;
}
for (i = 1; i <= vert; i++)
for (j = 1; j <= vert; j++) {
if (adj[i][j] == 0 && i != j)
adj[i][j] = INF; // यदि कोई एज नहीं है, तो इन्फिनिटी रखें
}
for (k = 1; k <= vert; k++)
for (i = 1; i <= vert; i++)
for (j = 1; j <= vert; j++)
adj[i][j] = min(adj[i][j], adj[i][k] + adj[k][j]); // k के माध्यम से i से j तक न्यूनतम पथ खोजें
cout << "Resultant adj matrix\n";
for (i = 1; i <= vert; i++) {
for (j = 1; j <= vert; j++) {
if (adj[i][j] != INF)
cout << adj[i][j] << " ";
}
cout << "\n";
}
return 0;
}
आउटपुट
Enter no of vertices: 3 Enter no of edges: 5 Enter the EDGE Costs: 1 2 8 2 1 12 1 3 22 3 1 6 2 3 4 Resultant adj matrix 0 8 12 10 0 4 6 14 0
