C/C++最佳算法perfom Adjacency2Distance矩陣[弗洛伊德-沃肖爾解決]

INITIAL ISSUE

好日子大家，C/C++最佳算法perfom Adjacency2Distance矩陣[弗洛伊德-沃肖爾解決]

我已經發現了幾個算法做這個任務。但是，所有這些代碼都考慮每個節點或邊的權重值。

我的目標是比這更容易，這是從相鄰一個獲得距離矩陣。

輸入將是：

a b c d e f connected vertices to i 
a 0 1 0 0 0 0 1 
b 1 0 1 1 0 0 3 
c 0 1 0 0 0 0 1 
d 0 1 0 0 1 0 2 
e 0 0 0 1 0 1 2 
f 0 0 0 0 1 0 1 
       --- 
      Sum: 10 -> Edges = Sum/2 = 5

輸出將是：提前任何建議

a b c d e f 
a 0 1 2 2 3 4 
b 1 0 1 1 2 3 
c 2 1 0 2 3 4 
d 2 1 2 0 1 2 
e 3 2 3 1 0 1 
f 4 3 4 2 1 0

感謝，

大衛·亞歷杭德羅。

SOLUTION FOUND

弗洛伊德 - 沃肖爾Kernell用C

for (k = 0; k < n; ++k) 
{ 
    for (i = 0; i < n; ++i) 
    { 
     for (j = 0; j < n; ++j) 
     { 
      if ((dist[i][k] * dist[k][j] != 0) && (i != j)) 
      { 
       if ((dist[i][k] + dist[k][j] < dist[i][j]) || (dist[i][j] == 0)) 
       { 
        dist[i][j] = dist[i][k] + dist[k][j]; 
       } 
      } 
     } 
    }     
}

來源

2012-06-12 Another.Chemist

也許重複的http://stackoverflow.com/questions/10079876/converting-a-adjacency-matrix-to-a-distance-or-hop-matrix – ffao

迄今爲止的理論最好似乎是'O（n 2 log N）'（見http://www.waset.org/journals/ijcms/v3/v3-5-43.pdf），但我無法真正瞭解它。 – ffao

Floyd- * Warshall * with a W;） – Pablo

如果您已經發現算法只重量協會去做，使用它們，但每次重設置爲1

BFS在任何情況下都是我的建議。

來源

2012-06-12 21:40:12 NominSim

好的建議。對於基本需求，最好的方法是深入！ –

變化零爲「無限」（即比任何合理的距離大）在鄰接矩陣值，然後運行對所得到的矩陣Floyd-Warshall。

NominSim建議的BFS將需要從每個起始頂點運行，以便獲得距離爲所有頂點。

來源

2012-06-12 21:51:44 Pablo

Floyd-Warshall - > O（n³） – Thomash

BFS n次 - > O（n²） – Thomash

BFS n次 - > O（mn +n²）Floyd-Warshall比代碼更容易編碼 – ffao

C/C++最佳算法perfom Adjacency2Distance矩陣[弗洛伊德-沃肖爾解決]

回答

相關問題