C++ Program to Find All Pairs Shortest Path

This C++ Program to Find All Pairs Shortest Path in a Graph.

Here is source code of the C++ Program to Find All Pairs Shortest Path using Floyd’s Algorithm. The C++ program is successfully compiled and run on a Linux system. The program output is also shown below.

  1. /*
  2.  * C++ Program to Find All Pairs Shortest Path
  3.  */
  4. #include <iostream>
  5. #include <cstdlib>
  6. #define max 10
  7. #define infi 999
  8. using namespace std;
  9. int p[max][max];
  10. /*
  11.  * All Pairs Shortest Path using Floyd's Algorithm
  12.  */
  13. void allpairshort(int a[max][max], int n)
  14. {
  15.     int k, i, j;
  16.     for (k = 0; k < n; k++)
  17.     {
  18.         for (i = 0; i < n; i++)
  19.         {
  20.             for (j = 0; j < n; j++)
  21.             {
  22.                 if (a[i][k] + a[k][j] < a[i][j])
  23.                 {
  24.                     a[i][j] = a[i][k] + a[k][j];
  25.                     p[i][j] = k;
  26.                 }
  27.             }
  28.         }
  29.     }
  30. }
  31.  
  32. /*
  33.  * Storing the shortest path
  34.  */
  35. void shortest(int i, int j)
  36. {
  37.     int k = p[i][j];
  38.     if (k > 0)
  39.     {
  40.         shortest(i, k);
  41.         cout<<"  "<<k<<"  ";
  42.         shortest(k, j);
  43.     }
  44. }
  45. /*
  46.  * Display the Shortest Path
  47.  */
  48. void findpath(int a[max][max], int i, int j, int n)
  49. {
  50.     cout<<"Path from " << i <<" to "<< j << ":";
  51.     if (a[i][j]  < infi)
  52.     {
  53.             cout<<"  "<<i<<"  ";
  54.             shortest(i, j);
  55.             cout<<"  "<<j<<" ";
  56.     }
  57. }
  58. /*
  59.  * Main Contains Menu
  60.  */
  61. int main()
  62. {
  63.     int i, j;
  64.     int a[][10] =  {{0, 10, infi, 30, 100},
  65.                 {infi, 0 , 50, infi, infi},
  66.                 {infi, infi , 0, infi, 10},
  67.                 {infi, infi , 20, 0, 60},
  68.                 {infi, infi , infi, infi, 0},
  69.                 };
  70.  
  71.     allpairshort(a, 5);
  72.     findpath(a, 0, 4, 5);
  73.     return 0;
  74. }

$ g++ allpairshortestpath.cpp
$ a.out
Path from 0 to 4:  0    3    2    4
 
------------------
(program exited with code: 1)
Press return to continue

Sanfoundry Global Education & Learning Series – 1000 C++ Programs.

advertisement
advertisement
If you wish to look at all C++ Programming examples, go to C++ Programs.

If you find any mistake above, kindly email to [email protected]

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 & discussions at Telegram SanfoundryClasses.