Johnson’s Algorithm in C

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.

```
#include<stdio.h>
```
```
#include<conio.h>
```
```
 
```
```
int min(int a, int b);
```

int cost[10][10], a[10][10], i, j, k, c;

```
 
```
```
int main(int argc, char **argv) {
```
```
    int n, m;
```
```
    printf("Enter no of vertices: \n");
```
```
    scanf("%d", &n);
```
```
    printf("\nEnter no od edges: \n");
```
```
    scanf("%d", &m);
```
```
    printf("\nEnter the\nEDGE Cost\n");
```
```
    for (k = 1; k <= m; k++) {
```
```
        scanf("%d", &i);
```
```
        scanf("%d", &j);
```
```
        scanf("%d", &c);
```
```
        a[i][j] = cost[i][j] = c;
```
```
    }
```
```
    for (i = 1; i <= n; i++)
```
```
        for (j = 1; j <= n; j++) {
```
```
            if (a[i][j] == 0 && i != j)
```
```
                a[i][j] = 31999;
```
```
        }
```
```
    for (k = 1; k <= n; k++)
```
```
        for (i = 1; i <= n; i++)
```
```
            for (j = 1; j <= n; j++)
```

                a[i][j] = min(a[i][j], a[i][k] + a[k][j]);

    printf("Resultant adjacency matrix\n");

```
    for (i = 1; i <= n; i++) {
```
```
        for (j = 1; j <= n; j++) {
```
```
            if (a[i][j] != 31999)
```
```
                printf("%d ", a[i][j]);
```
```
        }
```
```
        printf("\n");
```
```
    }
```
```
    return 0;
```
```
}
```
```
int min(int a, int b) {
```
```
    if (a < b)
```
```
        return a;
```
```
    else
```
```
        return b;
```
```
}
```

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.

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

« Prev - C Program to Find K Closest Median Elements

» Next - Preorder Traversal of a Binary Tree using Recursion in C

Related Posts:

Recommended Articles: