这个问题是典型的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 (冷色铅笔)》之铭言： : 假设有Ｎ个点，每个点相互之间有些有连结，有些没有连结。 : 给你一个Ｎ乘Ｎ的矩阵，代表每个点相互之间连结的有或无。 : 请算出每个点与点之间的最小连结步数， : 例如点１与点２有连结，点２与点３之间有连结，而点１与点３之间没有直接连结， : 则点１与点３之间的最小连结步数即为２步。 : 老师并不要求我写出来，所以我不是为了应付作业而来发问的。 : 这个程式的结构我想了很久，但没有想出来。 --

※ 发信站: 批踢踢实业坊(ptt.cc) ◆ From: 140.112.213.158