请问有现存的最短路径演算法满足以下条件的吗？ 1. node 可以重复 2. link 不可以重复 最短路径演算法的比较我都已经忘光光了 XDDDDDD 假设我们已经知道上面这种演算法好了，先叫他作 A1 那我们可以根据这个演算法实作出一个变形， 除了起点 s 跟终点 e ，还可以接受第三个参数 "必经点" c， 我们叫这个演算法 A2。 A2 的方法是把 c 分开成两点, c' 跟 c", (c消失) c' 跟 c" 中间加上一条 link CL, CL 的 weight 极低， 而所有本来跟 c 相邻的 node, 我们加上 link 使其依然跟 c', c" 相邻， 这样只要对 s 跟 e 作 A1, 得到的路径就一定会经过 CL。 现在我们已经有 A2， 提供以下功能：找到 s 经过 c 到 e 的最短路径。 此时令起点为 S，终点为 S，必经点为 E， 就可以求得一个从 S 出发跟结束, 而且一定经过 E 的 loop. 这个 loop 在 S 跟 E 的两边的部分，就是所求的两条路径。 (路径和最短,没有重复的link,且起点跟终点相同.) 然後是 S1 → E1, S2 → E2 这题... 在 E1 跟 S2 中间加一条 link T, weight 极低 施行 A1 ( S1, E2 ), 一定会经过 T, 就可以得到一条 S1 → E1 → S2 → E2 的路径， 紫色部分就是答案。 ============================================================ 这样有没有错？ 我不知道 XDDDDDDDD -- To iterate is human, to recurse is divine. 递回只应天上有, 凡人该当用回圈. 　 L. Peter Deutsch --

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