检查给定的距离矩阵是否代表有效的加权有向图

Question

给定距离矩阵D，其中d [i] [j]表示从i到j的最短路径，并且所有边缘权重都是正的。也，

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

距离矩阵可以表示或不表示有效的加权有向图。如何检查它是否代表有效的加权有向图？

Answer 1

以下条件是必要的但不充分：

• 对角线应为零（d [i] [j] == 0，其中i == j）
• 对于所有a，b（d [i] [j] == d [j] [i]，a到b和b到a的距离必须相同，其中i！= j）

对于有效距离矩阵，应满足以下条件：

• 如果从a到b的距离是d [a] [b]，并且从b到c的距离是d [b] [c]那么d [a] [c] <= d [a] [b] + d [b] [c]因为d [i] [j]表示i和j节点之间的最小距离。

伪代码：

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

检查是否

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

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

现在，在给定的最短路径上运行dijkstra的最短路径算法。这将给出一个新的最短路径矩阵，如A.

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

如果这些条件中的任何一个失败，则图形无效，否则它是有效的