Floyd-Warshall algorithm not finding length of shortest paths correctly

Question

This is probably a bad question to ask on SO since my rep is so low, but I have been looking through other solutions for hours, and my code seems nearly identical to the working solutions that I've come across. Please do not ignore the question based on low rep.

The output matrix, d[][] contains the (incorrect) lengths of the shortest paths between a given pair of vertices. The solution provided in the networkx library for Python has been used.

As an excerpt, the results for n=20 have been provided. I'm not printing out the paths greater than infinity (i.e. 99999), since there is overflow.

This is what the graph looks like:

---

My Floyd-Warshall algorithm implementation (C)

20  0   2
20  1   6
20  2   9
20  3   9
20  4   8
20  5   10
20  7   2
20  8   7
20  9   10
20  11  5
20  12  2
20  13  7
20  14  6
20  15  17
20  17  4
20  18  5

---

Networkx solution to Floyd-Warshall algorithm (Python)

20  0   2
20  1   5
20  2   4
20  3   4
20  4   3
20  5   7
20  7   2
20  8   2
20  9   4
20  11  4
20  12  2
20  13  6
20  14  5
20  15  4
20  17  3
20  18  4
20  20  0

---

Implementation:

#include <time.h>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h> 
#include <limits.h>

#define INF 9999
#define min(a,b) (a>b)?b:a;

int n;
/*
* Method signatures
*/
void shortestPath(int matrix[][n]);

int main(){
    char buf[16], c;
    int i, j, weight, ret;

    /* Open file handler for file containing test data */
    FILE *file = fopen("eg2.txt", "r");
    if(file==NULL){
        puts("I/O error: cannot read input file");
        fclose(file);
        exit(1);
    }
    /* Get number of vertices in file */
    fscanf(file, "%d", &n);

    /* Initialise matrix of n*3 elements */
    int matrix[n][n];
    memset(matrix, INF, n*n*sizeof(int));

    while((ret = fscanf(file, "%d %d %d", &i, &j, &weight)) != EOF) {
        if(ret == 3){
            matrix[i][j]=weight;
        } else {
            printf("ERROR: retrieved %d values (expecting 3)\n", ret);
            break;
        }
    }
    fclose(file);

    /* Output matrix */
    for(i=0; i<n; i++){
        matrix[i][i]=0;
        for(j=0; j<n; j++){
            printf("%d  ", matrix[i][j]);
        }
        printf("\n");
    }
    shortestPath(matrix);
}
/*
* Implementation of the Floyd-Warshall path finding algorithm
*/
void shortestPath(int matrix[][n]){
    int d[n][n], k, i, j;

    /* Copy values from matrix[][] to d[][] */
    for(i=0; i<n; i++){
        for(j=0; j<n; j++){
            d[i][j] = matrix[i][j];
        }
    }
    for(k=0; k<n; k++){
        for(i=0; i<n; i++){
            for(j=0; j<n; j++){
                if (d[i][k] + d[k][j] < d[i][j]){
                    d[i][j] = d[i][k] + d[k][j];
                }
            }
        }
    }
    for(i=0; i<n; i++){
        for(j=0; j<n; j++){
            if((d[i][j]!=0)&&(d[i][j]<INF)){
                printf("%d\t%d\t%d\n", i, j, d[i][j]);
            }
        }
    }
}

---

Test client (Python)

#!/usr/bin/python2.7
try:
    import matplotlib.pyplot as plt
    from collections import defaultdict
    import networkx as nx
    import numpy as np
except:
    raise

nodes = defaultdict(dict)
with open('eg2.txt', 'r') as infile:
    for line in infile.readlines()[1:]:
        line = map(int, line.split())
        src = line[0]
        dst = line[1]
        weight = line[2] 
        nodes[src][dst]=weight

G = nx.Graph()

for i in nodes:
    for j in nodes[i]:
        G.add_edge(i, j, weight=nodes[i][j])

rs = nx.floyd_warshall(G)
for i in rs:
    for j in rs[i]:
        print "%d\t%d\t%d" % (i, j, rs[i][j])

pos = nx.shell_layout(G)
nx.draw(G, pos, node_size=500, node_color='orange', edge_color='blue', width=1)

plt.axis('off')
plt.show()

Answer 1

Here is a complete solution for you. I used @pts's suggestion of using a fixed array, and the suggestion from the comments of initializing the array explicitly with a pair of nested loops. I also took some liberties with the way the algorithm works - for example, with the option to have either directed or undirected graphs - and show how you can include some intermediate outputs to help in the debugging.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define INF 9999
#define MIN(a,b)((a)<(b))?(a):(b)
// uncomment the next line to make processing symmetrical
// i.e. undirected edges
// #define SYM

#define NMAX 20
int n;

void shortestPath(int m[NMAX][NMAX]);
void printMatrix(int m[NMAX][NMAX]);

// implementation of floyd-warshall algorithm
// with minimal error checking
// input file = series of nodes on graph in form
// start, end, length
// algorithm attempts to find shortest path between any connected nodes
// by repeatedly looking for an intermediate node that shortens the current distance
// graphs are directional - 3 4 5 does not imply 4 3 5
// this can be changed by uncommenting the #define SYM line above
// also, hard coded to have no more than 20 nodes - defined with NMAX above
// path to input file is hard coded as "eg2.txt"

int main(void) {
  int i, j, weight, ret;

// open input file:
  FILE *fp = fopen("eg2.txt", "r");
  if(fp == NULL) {
    printf("cannot read input file\n");
    exit(1);
  }
// read number of nodes in the graph:
  fscanf(fp, "%d", &n);
  if(n > NMAX) {
    printf("input too large\n");
    fclose(fp);
    exit(1);
  }
  printf("n is %d\n", n);

// generate matrix:
  int matrix[NMAX][NMAX];
  for(i=0; i<NMAX;i++)
    for(j=0; j<NMAX; j++)
      matrix[i][j] = INF;

  while( (ret = fscanf(fp, "%d %d %d", &i, &j, &weight)) != EOF) {
    if(ret == 3) {
      matrix[i][j] = weight;
#ifdef SYM
      matrix[j][i] = weight;
#endif
    }
  else printf("error reading input\n");
  }
  fclose(fp);

  printMatrix(matrix);
  shortestPath(matrix);
  printMatrix(matrix);

}
void printMatrix(int m[NMAX][NMAX]) {
  int i, j;
  for(i=0; i<n; i++) {
    for(j=0; j<n; j++) {
      if(m[i][j]==INF) printf("  - "); else printf("%3d ", m[i][j]);
    }
    printf("\n");
  }

}

void shortestPath(int d[NMAX][NMAX]) {
  int i, j, k, temp;
  // no need to make a copy of the matrix: operate on the original
  for(k=0; k<n; k++) {
    for(i=0; i<n-1; i++) {
      for(j=0; j<n; j++) {
        if(i==j) continue; // don't look for a path to yourself...
        if(d[i][k] == INF || d[k][j]==INF) continue; // no path if either edge does not exist
        if((temp = d[i][k] + d[k][j]) < d[i][j]) {
          d[i][j] = temp;
#ifdef SYM
          d[j][i] = temp;
#endif
          printf("from %d to %d is shorter via %d: %d + %d is %d\n", i, j, k, d[i][k], d[k][j], temp);
        }
      }
    }
  }
  for(i=0; i<n; i++) {
    for(j=0; j<n; j++) {
      if(d[i][j] < INF) printf("%2d %2d %3d\n", i, j, d[i][j]);
    }
  }
}

With the following input file:

5
1 2 3
2 4 2
1 4 8
0 3 7
3 1 2
1 4 2
1 3 1
0 1 1

I got as output:

n is 5
  -   1   -   7   - 
  -   -   3   1   2 
  -   -   -   -   2 
  -   2   -   -   - 
  -   -   -   -   - 
from 0 to 2 is shorter via 1: 1 + 3 is 4
from 0 to 3 is shorter via 1: 1 + 1 is 2
from 0 to 4 is shorter via 1: 1 + 2 is 3
from 3 to 2 is shorter via 1: 2 + 3 is 5
from 3 to 4 is shorter via 1: 2 + 2 is 4
 0  1   1
 0  2   4
 0  3   2
 0  4   3
 1  2   3
 1  3   1
 1  4   2
 2  4   2
 3  1   2
 3  2   5
 3  4   4
  -   1   4   2   3 
  -   -   3   1   2 
  -   -   -   -   2 
  -   2   5   -   4 
  -   -   -   -   - 

Oddly enough, when I ran your code (as posted above) it gave me the same solution - although the output for the first part made it very clear that the memset wasn't working as you expected:

0  1  252645135  7  252645135  
252645135  0  3  1  2  
252645135  252645135  0  252645135  2  
252645135  2  252645135  0  252645135  
252645135  252645135  252645135  252645135  0  
0   1   1
0   2   4
0   3   2
0   4   3
1   2   3
1   3   1
1   4   2
2   4   2
3   1   2
3   2   5
3   4   4

In fact, the number that is being written to the matrix with the memset operation is 0x0F0F0F0F, which is 252645135 in decimal. You can understand why this is so by looking at the syntax of memset:

void *memset(void *str, int c, size_t n)
Parameters
str -- This is pointer to the block of memory to fill.

c -- This is the value to be set. The value is passed as an int, but the function fills the block of memory using the unsigned char conversion of this value.
n -- This is the number of bytes to be set to the value.

and combining with the hexadecimal representation of 9999, which is

0x270F

The "unsigned char conversion" of an int is that number modulo 256, or the least significant byte. In this case, the least significant byte is 0x0F and that is the value that gets written (repeatedly) to every byte in the block - hence the value 0x0F0F0F0F (on my machine, an int is four bytes long).

Afterword
Finally - if you want to use "any size of array", you can add the following couple of functions to your program - and replace the function signatures as indicated. This is a "tricky" way to create a two D array of variable size in C - essentially, when C comes across a pointer of the type int** it will dereference twice. By making this pointer-to-a-pointer point to a block of pointers to the block of memory, you create in effect a 2D array that the compiler can understand.

int **make2D(int r, int c) {
  int ii, **M;
  M = malloc(r * sizeof(int*) );
  M[0] = malloc( r * c * sizeof(int) );
  for(ii=1; ii<r; ii++) M[ii] = M[0] + ii * c * sizeof(int);
  return M;
}

void free2D(int** M) {
  free(M[0]);
  free(M);
}

Now you generate your matrix with

int **matrix;
matrix = make2D(n, n);

and you change the function signatures to

void shortestPath(int **m);
void printMatrix(int **m);

And call them with

shortestPath(matrix); // etc

To make everything work properly you have to make a few other adjustments in your code (example: you should not try to assign INF to all elements of a NMAX by NMAX array when you allocated less memory than that). You can try to figure this out for yourself - but just in case, here is the complete code. One other change I made - I got rid of n as a global variable and made it local to main (and passed it to the various routines that needed it). This is usually a good practice - it's all too easy to mix things up with globals, so use them only when you really have no choice.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define INF 9999
#define MIN(a,b)((a)<(b))?(a):(b)
// uncomment the next line to make processing symmetrical
// i.e. undirected edges
// #define SYM

void shortestPath(int **m, int n);
void printMatrix(int **m, int n);

// create 2D matrix of arbitrary (variable) size
// using standard C:
int **make2D(int r, int c) {
  int ii, **M;
  M = malloc(r * sizeof(int*) );
  M[0] = malloc( r * c * sizeof(int) );
  for(ii=1; ii<r; ii++) M[ii] = M[0] + ii * c * sizeof(int);
  return M;
}

void free2D(int** M) {
  free(M[0]);
  free(M);
}

// implementation of floyd-warshall algorithm
// with minimal error checking
// input file = series of nodes on graph in form
// start, end, length
// algorithm attempts to find shortest path between any connected nodes
// by repeatedly looking for an intermediate node that shortens the current distance
// graphs are directional - 3 4 5 does not imply 4 3 5
// this can be changed by uncommenting the #define SYM line above
// also, hard coded to have no more than 20 nodes - defined with NMAX above
// path to input file is hard coded as "eg2.txt"

int main(void) {
  int i, j, n, weight, ret;

// open input file:
  FILE *fp = fopen("eg2.txt", "r");
  if(fp == NULL) {
    printf("cannot read input file\n");
    exit(1);
  }
// read number of nodes in the graph:
  fscanf(fp, "%d", &n);
  printf("n is %d\n", n);

// generate matrix:
  int **matrix;
// allocate memory:
  matrix = make2D(n, n);
// fill all elements with INF:
  for(i=0; i<n;i++)
    for(j=0; j<n; j++)
      matrix[i][j] = INF;

// read the input file:
  while( (ret = fscanf(fp, "%d %d %d", &i, &j, &weight)) != EOF) {
    if(ret == 3) {
      matrix[i][j] = weight;
#ifdef SYM
// if undirected edges, put in both paths:
      matrix[j][i] = weight;
#endif
    }
  else printf("error reading input\n");
  }
  fclose(fp);

  printMatrix(matrix, n);
  shortestPath(matrix, n);
  printMatrix(matrix, n);

}
void printMatrix(int **m, int n) {
  int i, j;
  for(i=0; i<n; i++) {
    for(j=0; j<n; j++) {
      if(m[i][j]==INF) printf("  - "); else printf("%3d ", m[i][j]);
    }
    printf("\n");
  }

}

void shortestPath(int **d, int n) {
  int i, j, k, temp;
  // no need to make a copy of the matrix: operate on the original
  for(k=0; k<n; k++) {
    for(i=0; i<n-1; i++) {
      for(j=0; j<n; j++) {
        if(i==j) continue; // don't look for a path to yourself...
        if(d[i][k] == INF || d[k][j]==INF) continue; // no path if either edge does not exist
        if((temp = d[i][k] + d[k][j]) < d[i][j]) {
          d[i][j] = temp;
#ifdef SYM
          d[j][i] = temp;
#endif
          printf("from %d to %d is shorter via %d: %d + %d is %d\n", i, j, k, d[i][k], d[k][j], temp);
        }
      }
    }
  }
  for(i=0; i<n; i++) {
    for(j=0; j<n; j++) {
      if(d[i][j] < INF) printf("%2d %2d %3d\n", i, j, d[i][j]);
    }
  }
}

Answer 2

Don't use dynamically sized arrays (e.g. non-constant n in the array size), they may not work the way you think. One simple way to fix your code:

#define MAXN 100
int n;
...
  int matrix[MAXN][MAXN];
  scanf("%d", &n);
  if (n < 1 || n > MAXN) abort();
...
void shortestPath(int matrix[][MAXN]) {

Please recompile your code with all warnings enabled (e.g. gcc -W -Wall -Wextra -ansi), fix all the warnings, and indicate in the question that your code compiles without emitting any warning.