Home » Data Structure

Modified Warshall's algorithm to find shortest path matrix

In this example, we will learn about weighted graph with positive and negative weights, shortest path and Warshall’s algorithm. By Manu Jemini, on January 09, 2018

Image source: http://mathworld.wolfram.com/images/eps-gif/GraphNodesEdges_1000.gif

Weighted graph

A weighted graph with positive and negative weights can be understood as a graph with edges having cost. Edge is the line connecting two nodes or a pair of nodes. The cost can be positive or negative.

Image source: https://i.stack.imgur.com/GlrNb.png

Shortest distance

The shortest distance is the distance between two nodes. For Example, to reach a city from another, can have multiple paths with the different number of costs. A path with the minimum possible cost is the shortest distance.

Image source: https://i.stack.imgur.com/tyTz7.png

Warshall's algorithm

Warshall's algorithm is an algorithm which is used to find the shortest path between the source and destination nodes. These types of problems generally solved with BST if the cost of every edge is 1. But here the edges can have different values, even negative values. Hence we need to use this algorithm.

C program to find shortest path matrix using modified Warshall's algorithm

#include <stdio.h>

#define infinity 9999
#define MAX 20

int minimum(int a, int b) {
  if (a <= b)
    return a;
  else
    return b;
} /*End of minimum()*/

int display(int matrix[MAX][MAX], int n) {
  int i, j;
  for (i = 0; i < n; i++) {
    for (j = 0; j < n; j++)
      printf("%7d", matrix[i][j]);
    printf("\n");
  }
} /*End of display()*/

int main() {
  int i, j, k, n;
  int adj[MAX][MAX], path[MAX][MAX];

  printf("Enter number of vertices : ");
  scanf("%d", & n);

  printf("Enter weighted matrix :\n");
  for (i = 0; i < n; i++)
    for (j = 0; j < n; j++)
      scanf("%d", & adj[i][j]);

  printf("Weighted matrix is :\n");
  display(adj, n);

  /*Replace all zero entries of adjacency matrix with infinity*/
  for (i = 0; i < n; i++)
    for (j = 0; j < n; j++)
      if (adj[i][j] == 0)
        path[i][j] = infinity;
      else
        path[i][j] = adj[i][j];

  for (k = 0; k < n; k++) {
    printf("Q%d is :\n", k);
    display(path, n);
    for (i = 0; i < n; i++)
      for (j = 0; j < n; j++)
        path[i][j] = minimum(path[i][j], path[i][k] + path[k][j]);
  }
  
  printf("Shortest path matrix Q%d is :\n", k);
  display(path, n);
  
  return 0;
} /*End of main() */

Output