# 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, a, 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

0 4 6
5 0 2
3 7 0```

Sanfoundry Global Education & Learning Series – 1000 C Programs.

Note: Join free Sanfoundry classes at Telegram or Youtube 