水木社区手机版
- 主题:弗洛伊德算法有一点不太懂
- 很容易错写成i、j、k的循环
【 在 zhrb 的大作中提到: 】
: 里面两层循环是遍历每个点对。外面那个循环k指的是每加入1个新点k，然后i-k-j会
: 不会比i-j更小。
: 所以显然啊
: ...................
--
FROM 218.108.223.* - 基于最短+1，还是最短。
【k放在最外层】，内2层念做：x经0到达y
k=0时
x和y本来不通，若x和y经0相通，则x经0到y最短。
得到一条经0的的最短路径。得到所有经0的最短路径。
递推，
k=x时，p经x到y，最短。
因为p到x最短，x到y最短。
【k放在最内层】；外2层读作：x经(1..n)到y;
对任意起点x, 从(1..n)中取k ，若k>x，则经k节点的所有通路还没构造。所以
x到k，不一定是最短；
k到y，不一定是最短；
x经k到y，不一定最短。
直觉、理解、验证（比如画更新图）、证明是不同层次。
我这个是直觉，最浅。
【 在 ooolinux 的大作中提到: 】
: void floyd() {
: for (int k = 0; k < n; k++) {
: for (int i = 0; i < n; i++) {
: ...................
--
修改:DoorWay FROM 202.100.34.*
FROM 202.100.34.* - 递推那里，p是什么？
【 在 DoorWay 的大作中提到: 】
: 基于最短+1，还是最短。
:
: 【k放在最外层】，内2层念做：x经0到达y
: k=0时
: x和y本来不通，若x和y经0相通，则x经0到y最短。
: 得到一条经0的的最短路径。得到所有经0的最短路径。
--发自 ismth(丝滑版)
--
FROM 112.50.54.* - 你不妨猜一个，是什么。我们好讨论。
也许我能明白你想问什么。
我这直觉版，不好再往下拆概念。
【 在 ooolinux 的大作中提到: 】
: 递推那里，p是什么？
:
--
FROM 36.40.208.* - 文字居然发不出来
【 在 DoorWay 的大作中提到: 】
:
--
修改:ooolinux FROM 218.108.223.*
FROM 218.108.223.* - 那就是懂了，现在没问题了吧。
【 在 ooolinux 的大作中提到: 】
: 文字居然发不出来
: [upload=1][/upload]
--
FROM 172.235.192.* - 没有那么清晰，可能我有点缺乏思考
【 在 DoorWay 的大作中提到: 】
: 那就是懂了，现在没问题了吧。
--
FROM 218.108.223.*