图的平均最优路径

我需要找到图的平均最优路径。我决定使用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;

来源

2013-04-12 user2057191

你在哪里定义'vertices'？ –

@JoeFrambach它们是在一个类中定义的，它们只是图中顶点的数量。 – user2057191

好了，全零的输出是正确的。

维基百科的文章说，你应该矩阵这样被初始化：

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 
     } 
    } 
}

来源

2013-04-12 05:03:59

谢谢！最后一点代码帮助了很多。 – user2057191

图的平均最优路径

回答

相关问题