首先非常感谢mantour大大的解释： 另外在此郑重的向mantour道个歉，当天投水球问问题时， 我的行为显得突兀冒失...... 希望mantour大人大量不予计较。 最後提出我对这个演算法的发现与疑问， 当i,j,k任两个为相同时，其路径长 D(i,j) 不会产生任何改变， 所以可以跳过这些情况，不必去考虑！ 虽然我现下了解这个演算法中，每个回圈的作用为何， 但我很疑惑的是，为什麽最外层Ｋ的顺序不影响最後之结果？ 这演算法其先运算的结果可能会在後运算时再次的被拿来运用。 例如，依回圈顺序 (a).k=3,j=2,i=5的执行顺序是在 (b).k=4,j=2,i=3之前， 假设(b)的情况是V3与V2之间可以透过V4来减少距离， 即　V3-><-V2 = inf　可由　V3-->V4-->V2 = 2　来取代。 但若(a)的情况是V5与V2之间无法透过V3来减少距离，且V5与V2之间无直接连结， 即　V5-><-V2 =inf　且(b)的情况仍未执行，所以　V3-><-V2 = inf ， 在这样的情形下，我们得到　V5-->V3-><-V2 = inf　， 而非真实情况下的　V5-->V3-->V4-->V2 = 3 。 以上是我自以为合理的推演，看起来最外层K的执行顺序会影响到最终的执行结果， 但我实际上操作的结果却没有这样的发现，这中间是否还有什麽我没弄懂的地方， 希望了解的大大可以为在下指点迷津！ 谢谢各位！ ※ 引述《mantour (朱子)》之铭言： : 这个问题是典型的dynamic programming的例子 : 基本上可以直接套用floyd最短路径演算法 : 就演算法的精神说明一下 : 一开始用一个矩阵D表示节点的相邻性 : D(i,i) = 0 : 若vi,vj之间有连结，则D(i,j)=1 : 若没有连结 : D(i,j) = Inf (Inf 为自设的常数，比任二点可能的最大步数大) : 此时D(i,j)表示了vi,vj直接相连的步数 : 接着考虑从vi走到vj，中间可以经过v1的最少步数 : 如果经过v1的步数比本来直接走短，就把D(i,j)重设为新路径的步数 : 也就是说对所有的i,j : if( D(i,1)+D(1,j) .lt. D(i,j)) then : D(i,j) = D(i,1) + D(1,j) : end if : 再来考虑vi,vj中间可经过v1,v2的最少步数 : 这里有一点tricky的地方是，我们不需要真的去算所有经过v1或v2的组合 : 只要分成二点来考虑就可以了的大小就可以了 : 1) 由vi到vj 可经可不经v1 但 不经v2 也不经过其他点 的最小步数 : 2) 由vi到vj 可经可不经v1 但 必须经过 v2 不经过其他点 的最小步数 : 只要比较这二个数值中比较小的就是由vi到vj 可经可不经v1,v2 的最少步数 : 其中 1)前面已经算过了，就是 目前的D(i,j) : 而2)呢？ 可以想一想，如果有一条最短的路线从 vi 经过 v2 到 vj : 中间可经可不经v1 但不可经过其他点 : 则其中由vi到v2和由v2到vj这二段分别一定也是走可经可不经v1 而不经其他点的最短路径 : 也就是 2) = D(i,2) + D(2,j) : 因此假如对所有i,j再进行一次重设 : if( D(i,2)+D(2,j) .lt. D(i,j)) then : D(i,j) = D(i,2) + D(2,j) : end if : 就得到任二点之间 可经可不经 v1,v2 ，但不经其他点的最短步数 : 重复这个动作 : 就可以得到任二点之间，可经可不经其他所有点 的最短步数 : 也就是我们要的答案 : 整个演算法写出来只需要三层回圈 : do k=1,N : do j=1,N : do i=1,N : if (D(i,k)+D(k,j) .lt. D(i,j)) then : D(i,j) = D(i,k) + D(k,j) : end if : end do : end do : end do : 时间复杂度为O(N^3) : 其中由於连结没有方向性，因此D是对称的，实际上只需计算上三角的部份即可 : 所以还可以再修改节省一点时间 : 打了半天好像还是讲得不是很清楚 : 不过只要把演算法的名字丢到google应该就可以找到更详细的说明 : 希望对原PO有帮助 : 也希望我有写错的地方大家可以帮我指出来 : ※ 引述《yin0416 (冷色铅笔)》之铭言： : : 假设有Ｎ个点，每个点相互之间有些有连结，有些没有连结。 : : 给你一个Ｎ乘Ｎ的矩阵，代表每个点相互之间连结的有或无。 : : 请算出每个点与点之间的最小连结步数， : : 例如点１与点２有连结，点２与点３之间有连结，而点１与点３之间没有直接连结， : : 则点１与点３之间的最小连结步数即为２步。 : : 老师并不要求我写出来，所以我不是为了应付作业而来发问的。 : : 这个程式的结构我想了很久，但没有想出来。 -- ◥ ◢◥◣ △ㄑ◤◢◥ ／◤〝 ▇▇ 〞◥＼ ◢ㄑ◥◣\ ◣ / \ ◣ \◤〝／／ ＼＼〞◣/ ◥◥◤◤◤◥◤◥◢ !◣ ◤◤◤)◥◥ ◤! ／＼ ／＼ ◣◤ 〒 〒 ◥◢ ◣◤ ● ● ◥◤ ── ／ ◣ —lm ◢ ◥◣"" v ""◢◤ ╱▇ ◣ ※╲ ◣ ◢◥ ◤◣ ψg80046 --

※ 发信站: 批踢踢实业坊(ptt.cc) ◆ From: 140.128.128.158 ※ 编辑: yin0416 来自: 140.128.128.158 (12/08 11:45) 抱歉，原来我误解了，已去掉那一句了！ 现在我正在人工观察中，谢谢建议！ ※ 编辑: yin0416 来自: 140.128.128.158 (12/08 15:13)