C Program to Implement Johnson’s Algorithm

This is a C Program to implement Johnson’s Algorithm. This code implements Johnson’s algorithm to solve the “all pairs shortest path” problem, ie. given an input graph with general edge weights (can be negative) with no negative cycles, find the shortest (u, w) path for all pairs of vertices (u, w). If the input graph has any negative cycles, the program will report this and halt (since there is no known polynomial time algorithm for finding shortest paths that avoid negative cycles).

Here is source code of the C Program to Implement Johnson’s Algorithm. 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<conio.h>
  3.  
  4. int min(int a, int b);
  5. int cost[10][10], a[10][10], i, j, k, c;
  6.  
  7. int main(int argc, char **argv) {
  8.     int n, m;
  9.     printf("Enter no of vertices: \n");
  10.     scanf("%d", &n);
  11.     printf("\nEnter no od edges: \n");
  12.     scanf("%d", &m);
  13.     printf("\nEnter the\nEDGE Cost\n");
  14.     for (k = 1; k <= m; k++) {
  15.         scanf("%d", &i);
  16.         scanf("%d", &j);
  17.         scanf("%d", &c);
  18.         a[i][j] = cost[i][j] = c;
  19.     }
  20.     for (i = 1; i <= n; i++)
  21.         for (j = 1; j <= n; j++) {
  22.             if (a[i][j] == 0 && i != j)
  23.                 a[i][j] = 31999;
  24.         }
  25.     for (k = 1; k <= n; k++)
  26.         for (i = 1; i <= n; i++)
  27.             for (j = 1; j <= n; j++)
  28.                 a[i][j] = min(a[i][j], a[i][k] + a[k][j]);
  29.     printf("Resultant adjacency matrix\n");
  30.     for (i = 1; i <= n; i++) {
  31.         for (j = 1; j <= n; j++) {
  32.             if (a[i][j] != 31999)
  33.                 printf("%d ", a[i][j]);
  34.         }
  35.         printf("\n");
  36.     }
  37.     return 0;
  38. }
  39. int min(int a, int b) {
  40.     if (a < b)
  41.         return a;
  42.     else
  43.         return b;
  44. }

Output:

$ gcc JohnsonsAlgorithm.c
$ ./a.out
 
Enter no of vertices: 5
 
Enter no od edges: 4
 
Enter the,
EDGE Cost
1 2 4
2 1 6
1 3 11
3 1 3
2 3 2
 
Resultant adjacency matrix
0 4 6 
5 0 2 
3 7 0

Sanfoundry Global Education & Learning Series – 1000 C Programs.

advertisement
advertisement

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

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.