Check if given distance matrix represents a valid weighted directed graph

Question

Given a distance matrix D where d[i][j] represents the shortest path from i to j and all edge weights are positive. Also,

d[i][i] = 0  and
d[i][j] > 0

The distance matrix may or may not represent a valid weighted directed graph. How to check if it represents a valid weighted directed graph?

Answer 1

The following conditions are necessary but not sufficient:

• diagonal should be zero (d[i][j]==0 where i==j)
• distance from a to b and b to a must be same for all a,b (d[i][j]==d[j][i] where i!=j)

The following condition should hold for valid distance matrix:

• if there is a distance from a to b is d[a][b] and also the distance from b to c is d[b][c] then d[a][c] <= d[a][b] + d[b][c] because d[i][j] represent min distance between i and j node.

Sudo Code:

bool valid = true;
for(int k=0;k<n;k++)
{
     for(int i=0;i<n;k++)
     {
         for(int j=0;j<n;j++)
         {
             if(j<=i) //check for only upper half of diagonal
                 continue;
             if(d[i][k]+d[k][j]<d[i][j])
             {
                 valid = false;
                 break;
             }
         }
         if(!valid)
             break;
     }
     if(!valid)
         break;
}
return valid;

Answer 2

Check if

   d[i][j]==0 for i=j and 

   d[i][j]==d[j][i] for all i and j

Now, run dijsktra's shortest path algorithm on the given shortest path. This will give a new shortest path matrix say A.

   Now check if d[i][j]=A[i][j] for all i and j.

If any of these conditions fail, graph is invalid,else it is valid