作者热门文章
- iOS/Objective-C 元类和类别
- objective-c - -1001 错误,当 NSURLSession 通过 httpproxy 和/etc/hosts
- java - 使用网络类获取 url 地址
- ios - 推送通知中不播放声音
使用以下论文第 4 页上的算法,我正在尝试计算所有对的最短路径矩阵。
http://www.waset.org/journals/ijcms/v3/v3-5-43.pdf
我对(算法的)第 7 行和第 8 行以及随后的第 11 和 12 行感到困惑,因为给 s1 赋值 j 并同时使用这两个第 8 行的比较对我来说似乎模棱两可。我是想知道我是否读错了缩进。我是算法新手,所以请耐心等待。
while(flag != false){
for(int i=0; i<n;i++){
aMin = Integer.MAX_VALUE;
bMin = Integer.MAX_VALUE;
for(int j=0; j<n;j++){
// Line 7 of the algorithm
if((distanceMatrix[i][j] < aMin) && (j != i) && (BR[i][j] == false)){
aMin = distanceMatrix[i][j];
BR[i][j] = true;
a[i] = j;
int s1 = j; // End of line 7
// Line 8 of the algorithm
if(distanceMatrix[i][j] < distanceMatrix[i][s1])
BR[i][s1] = false; // End of line 8
}
}
for(int j=0; j<n; j++){
// Line 11 of the algorithm
if((distanceMatrix[i][j] < bMin) && (j != i) && (j != a[i]) && (BR[i][j] == false)){
bMin = distanceMatrix[i][j];
BR[i][j] = true;
b[i] = j;
int s2 = j; // end of line 11
// Line 12 of the algorithm
if(distanceMatrix[i][j] < distanceMatrix[i][s2])
BR[i][s2] = false; // end of line 12
}
}
}
for(int i=0; i <n; i++){
for(int j=0; j<n; j++){
int t1 = distanceMatrix[i][a[i]] + distanceMatrix[a[i]][j];
int t2 = distanceMatrix[i][b[i]] + distanceMatrix[b[i]][j];
distanceMatrix[i][j] = Math.min(distanceMatrix[i][j], Math.min(t1,t2));
distanceMatrix[j][i] = distanceMatrix[i][j];
}
}
flag = true;
for(int i=0; i<n;i++){
// Line 19 of the algorithm
for(int j=0; j<n; j++){
temp[i][j] = distanceMatrix[i][j]; // end of line 19
// Line 20 of the algorithm
if (distanceMatrix[i][j] == temp[i][j])
flag = false; // end of line 20
}
}
}
此外,通过查看算法中的第 19 行和第 20 行,我了解到它会陷入循环,因为 flag 始终为真。
最佳答案
我觉得应该是这样的:
4) for i ← 1 to n do amin← ∞ ; bmin ← ∞
5) for j ← 1 to n do
6) if D[i, j] < amin and j = i and BR[i, j] = 0 then
7) amin ← D[i, j] ; BR[i, j] ← 1 ; a[i] ← j ; s1 ← j
8) if D[i, j] < D[i, s1] then BR[i, s1] ← 0
如您所见,s1
可能并不总是 j
: 它永远是 <= j
然而。
所以第二个if
不在里面头。否则,它没有意义,因为 s1 == j
总是,你不能拥有D[i, j] < D[i, j]
.
关于java - 所有对最短路径 Udaya Kumar Redd 算法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/11261919/
使用以下论文第 4 页上的算法,我正在尝试计算所有对的最短路径矩阵。 http://www.waset.org/journals/ijcms/v3/v3-5-43.pdf 我对(算法的)第 7 行和第
我是一名优秀的程序员,十分优秀!