圖的平均最優路徑

我需要找到圖的平均最優路徑。我決定使用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

圖的平均最優路徑

回答

相關問題