数学建模社区-数学中国

标题: 我终于勉强理解了弗洛伊德算法(我简称弗法)。 [打印本页]

---

作者: 释永思    时间: 2015-9-5 08:57
标题: 我终于勉强理解了弗洛伊德算法(我简称弗法)。
关于最短路径算法中的弗洛伊德算法：
我终于勉强理解了弗洛伊德算法(我简称弗法)。
迪杰斯特拉算法我二十年前已知，最近才了解弗法，感到很难理解。利用抗战纪念日放假期间，闭关冥想弗法。
我冥想出N步弗法，冥想出源码，但始终比网上源码多一重循环，为何网上源码是三重循环，我冥想者要在外面再套一层循环？这或许正是弗法精华乎？
后来冥想悟道，此象星云假说，六王毕四海一，蜀山兀阿房出，或许正弗法精华乎？
4 R* c4 ?! g# A1 j1 N2 J6 i% Q' B弗法中，凡处理k点时，必连通所有关联k点之原始点与原始边乎！这点可能是关键！于是顿悟，大明江山！
9 T8 k7 q; @  w# V" `* f
3 C8 q4 C- E# B6 c7 N
* z5 d' S% `8 i6 H9 K) B! G

---

作者: 释永思    时间: 2015-9-6 13:41
现在专心思考弗洛伊德算法，这个可能要用到数学归纳法来证明的，百度网上没有人讲到用数归法
来证明弗法的。
# ~5 w5 s6 Y3 k$ p

---

作者: qianlingwen    时间: 2015-9-10 14:37
我想我还是不明白
: T% u9 C4 a' K1 x0 E7 M" d/ Q

---

作者: 风靡全球    时间: 2015-9-10 17:54
加油
3 U4 C) O: G( T1 S: S' }. O" m0 x

---

作者: 风靡全球    时间: 2015-9-10 17:54
加油
/ ^7 Q- Y, F" L2 k; W

---

作者: 风靡全球    时间: 2015-9-10 17:54
加油
. g6 e) E  J4 L, L5 a" b7 m

---

作者: 风靡全球    时间: 2015-9-10 17:54
加油

---

作者: 风靡全球    时间: 2015-9-10 17:55
加油
' W! u% n6 }3 p( o$ h% n+ q

---

作者: 风靡全球    时间: 2015-9-10 17:55
加油
8 N. x6 x6 O0 q5 ~

---

作者: 风靡全球    时间: 2015-9-15 17:00
加油努力
$ t( t: k" h5 a* D

---

作者: 风靡全球    时间: 2015-9-16 18:00
加油  一定要努力哦

---

作者: 风靡全球    时间: 2015-9-16 18:00
加油  一定要努力哦
/ k, _' I, R6 l  L

---

作者: 风靡全球    时间: 2015-9-16 18:00
加油  一定要努力哦
' p  T$ @8 n& t; g; E$ J( D2 A% K

---

作者: 风靡全球    时间: 2015-9-16 18:01
加油  一定要努力哦
0 ^0 K  [5 K! A/ _

---

作者: 风靡全球    时间: 2015-9-16 18:01
加油  一定要努力哦
% C. ^/ K' q, |$ m, L- `. y

---

作者: 风靡全球    时间: 2015-9-16 18:01
加油  一定要努力哦

---

作者: 风靡全球    时间: 2015-9-16 18:01
加油  一定要努力哦

---

作者: 风靡全球    时间: 2015-9-16 18:01
加油  一定要努力哦

---

作者: 风靡全球    时间: 2015-9-16 18:01
加油  一定要努力哦
# ?& {1 a; Z/ G' D) c( a

---

作者: 风靡全球    时间: 2015-9-16 18:01
加油  一定要努力哦
8 a2 c0 M& O/ M- O+ R7 N1 s

---

作者: 释永思    时间: 2015-9-24 09:01
关于弗洛伊德算法的新证明：2015.09.23  经过弗法的三重循环后，任意两点之间的距离已是最短路。 仍用数学归纳法，假设N <= n时，弗法是正确的，要证明，N = n+1时，弗法仍是成立的。 设k = n+1是最后一点。 如果任意两点间的最短路径结过的顶点数是小于k的，那么根据假设知弗法正确是最短路的。 如果任意两点间的最短路径结过的顶点数是等于k的。那么知摘去最后3个顶点即只剩下(k-3)个点时，是N <= n的情形。 起点是a点,终点是b点,与k点直接相连的是c点,d点 。 当最外层第三重循环循环到最后三点k,c,d时，ac,bd已经连通了是N <= n的弗法情形。 k,c,d三点，无论哪个是先是后的组合，都必定能够令ab连通且最短路。 例如k点连通cd，c点连通ad,d点连通ab。 又如c点连通ak（ck不用c点连通，因为原始边长早已有数值早已连通）,k点连通ad,d点连通ab。 所以命题得证。

---

作者: zhwdiao    时间: 2015-9-24 09:02
加油，目前在看图论算法。
) t! _: ]* O- L

---

作者: G天土生金    时间: 2019-7-20 11:07
加油          ,

---

欢迎光临 数学建模社区-数学中国 (http://www.madio.net/)

Powered by Discuz! X2.5