c++ - 图的平均最优路径

Question

我需要找到图形的平均最优路径。我决定使用 Floyd-Warhsall 的算法来获得所有可能的最佳长度，但所有条目都被改写为零。关于如何解决此问题的任何想法？

原始矩阵:

0 0 0 0 1 0
0 0 1 0 4 0
0 1 0 0 0 2
0 0 0 0 0 1
1 4 0 0 0 2
0 0 2 1 2 0

平均代码:

double average = 0;
vector<vector<double> > p;
p = matrix;

for(int k = 0; k < vertices; k++)
{
    for(int i = 0; i < vertices; i++)
    {
        for(int j = 0; j < vertices; j++)
        {
            if((p[i][k] + p[k][j] < p [i][j]))
            {
                p[i][j] = p[i][k]+p[k][j];
            }
        }
    }
}

double sum = 0;

for(int i = 0;i < vertices; i++)
{
    for(int j = 0; j < vertices; j++)
    {
        sum += p[i][j]; //adds up all entries
    }
}

double fact = 0;
for(int i = 1; i < vertices; i++)
{
    fact += i;
}
average = sum/fact;

return average;

Answer 1

嗯，全零的输出是正确的。

维基百科文章说你的矩阵应该像这样初始化:

 0  inf inf inf  1  inf
inf  0   1  inf  4  inf
inf  1   0  inf inf  2
inf inf inf  0  inf  1
 1   4  inf inf  0   2
inf inf  2   1   2   0

因此在您的初始化步骤中，只需将它们设置为 INT_MAX。

你会得到零，因为当节点之间的权重为零时，这当然是微不足道的解决方案!

编辑:实际上，INT_MAX 是一个糟糕的选择，因为您要将它们中的两个相加。那是溢出。我想将它们设置为 INT_MAX/2 是安全的。除非您计划让权重大于 INT_MAX/2。

#include <cfloat>

for(int i = 0;i < vertices; i++)
{
    p[i][i] = 0; // diagonal should be initialized to zero.
    for(int j = 0; j < vertices; j++)
    {
        if ( i != j && p[i][j]==0)
        {
            p[i][j] = DBL_MAX / 2.0; // As close to infinity as we'll get
        }
    }
}