# C++ Program to Implement Johnson’s Algorithm

This is a C++ Program to implement Johnson’s Algorithm. Johnson’s algorithm helps to find shortest path between given source and destination nodes.

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<iostream>`
2. `#include<conio.h>`
3. ` `
4. `using namespace std;`
5. ` `
6. `int min(int a, int b);`
7. `int cost[10][10], a[10][10], i, j, k, c;`
8. ` `
9. `int min(int a, int b)`
10. `{`
11. `    if (a < b)`
12. `        return a;`
13. `    else`
14. `        return b;`
15. `}`
16. ` `
17. `int main(int argc, char **argv)`
18. `{`
19. `    int n, m;`
20. `    cout << "Enter no of vertices";`
21. `    cin >> n;`
22. `    cout << "Enter no of edges";`
23. `    cin >> m;`
24. `    cout << "Enter the\nEDGE Cost\n";`
25. `    for (k = 1; k <= m; k++)`
26. `    {`
27. `        cin >> i >> j >> c;`
28. `        a[i][j] = cost[i][j] = c;`
29. `    }`
30. `    for (i = 1; i <= n; i++)`
31. `        for (j = 1; j <= n; j++)`
32. `        {`
33. `            if (a[i][j] == 0 && i != j)`
34. `                a[i][j] = 31999;`
35. `        }`
36. `    for (k = 1; k <= n; k++)`
37. `        for (i = 1; i <= n; i++)`
38. `            for (j = 1; j <= n; j++)`
39. `                a[i][j] = min(a[i][j], a[i][k] + a[k][j]);`
40. `    cout << "Resultant adj matrix\n";`
41. `    for (i = 1; i <= n; i++)`
42. `    {`
43. `        for (j = 1; j <= n; j++)`
44. `        {`
45. `            if (a[i][j] != 31999)`
46. `                cout << a[i][j] << " ";`
47. `        }`
48. `        cout << "\n";`
49. `    }`
50. `    return 0;`
51. `}`

Output:

```\$ g++ JohnsonsShortestPath.cpp
\$ a.out

Enter no of vertices 3
Enter no of edges 5
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

------------------
(program exited with code: 0)

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