fork download
copy 
  1. //Kruskal's algorithm
  2. #include<bits//stdc++.h>
  3. using namespace std;
  4. #define pf printf
  5. #define sf scanf
  6. #define inf 999
  7. int main()
  8. {
  9.     int s=0;
  10.     pf("Enter no of nodes: \n");
  11.     int n ;
  12.     sf("%d",&n);
  13.     int a[n][n];
  14.     int c[n][n]= {0};
  15.     pf("Enter the weighted graph\nNote:999 for infinity\n");
  16.     for(int i = 0 ; i<n; i++)
  17.         for(int j = 0 ; j<n ; j++)
  18.         {
  19.             sf("%d",&a[i][j]);
  20.             c[i][j]=999;
  21.         }
  22.     pf("Given weighted graph is :\n");
  23.     for(int i = 0 ; i<n; i++)
  24.     {
  25.         for(int j = 0 ; j<n ; j++)
  26.         {
  27.             pf("%d ",a[i][j]);
  28.         }
  29.         pf("\n");
  30.     }
  31.     pf("\n");
  32.     int ti,tj,low;
  33.     for(int i =0 ; i<n-1; i++)
  34.     {
  35.         ti=inf;
  36.         tj=inf;
  37.         low=inf;
  38.         for(int l = 0; l<n; l++)
  39.         {
  40.             for(int m=0; m<n; m++)
  41.             {
  42.                 if(low>a[l][m]&&(c[l][m]==999)&&a[l][m]!=0)
  43.                 {
  44.                     low =a[l][m];
  45.                     ti=l;
  46.                     tj=m;
  47.                 }
  48.             }
  49.         }
  50.         c[ti][tj]=low;
  51.         c[tj][ti]=low;
  52.         //floyd's algo
  53.         for(int i = 0 ; i <n ; i++)
  54.         {
  55.             int tem[n][n];
  56.             for(int k = 0 ; k<n ; k++)
  57.             {
  58.                 for(int l = 0 ; l<n ; l++)
  59.                 {
  60.                     int t = 0;
  61.                     if(k==l)
  62.                     {
  63.                         tem[k][l]=0;
  64.                     }
  65.                     else if(k==i||l==i)
  66.                     {
  67.                         tem[k][l]=c[k][l];
  68.                     }
  69.                     else
  70.                     {
  71.                         t= c[k][i]+c[i][l];
  72.                         if(t<c[k][l]&&c[k][l]!=0)
  73.                         {
  74.                             tem[k][l] = t;
  75.                         }
  76.                         else
  77.                         {
  78.                             tem[k][l] = c[k][l];
  79.                         }
  80.                     }
  81.                 }
  82.             }
  83.             for(int i = 0 ; i<n; i++)
  84.             {
  85.                 for(int j = 0 ; j<n ; j++)
  86.                 {
  87.                     c[i][j]=tem[i][j];
  88.                 }
  89.             }
  90.         }
  91.         //floyd's algo
  92.         s=s+low;
  93.         pf("%d<->%d, %d\n",ti,tj,low);
  94.     }
  95.     pf("shortest path is %d\n",s);
  96.     return 0 ;
  97. }
  98. /*
  99. 6
  100. 0
  101. 4
  102. 4
  103. 999
  104. 999
  105. 999
  106. 4
  107. 0
  108. 2
  109. 999
  110. 999
  111. 999
  112. 4
  113. 2
  114. 0
  115. 3
  116. 1
  117. 6
  118. 999
  119. 999
  120. 3
  121. 0
  122. 999
  123. 2
  124. 999
  125. 999
  126. 1
  127. 999
  128. 0
  129. 3
  130. 999
  131. 999
  132. 6
  133. 2
  134. 3
  135. 0
  136. */
  137.  
Success #stdin #stdout 0.01s 5552KB
comments (?)
stdin
copy 
6
0
4
4
999
999
999
4
0
2
999
999
999
4
2
0
3
1
6
999
999
3
0
999
2
999
999
1
999
0
3
999
999
6
2
3
0
stdout
copy 
Enter no of nodes: 
Enter the weighted graph
Note:999 for infinity
Given weighted graph is :
0 4 4 999 999 999 
4 0 2 999 999 999 
4 2 0 3 1 6 
999 999 3 0 999 2 
999 999 1 999 0 3 
999 999 6 2 3 0 

2<->4, 1
1<->2, 2
3<->5, 2
2<->3, 3
0<->1, 4
shortest path is 12
https://ideone.com/NW73RN
language:
C++14 (gcc 8.3)
created:
1 year ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!