数学建模社区-数学中国
标题:
我终于勉强理解了弗洛伊德算法(我简称弗法)。
[打印本页]
作者:
释永思
时间:
2015-9-5 08:57
标题:
我终于勉强理解了弗洛伊德算法(我简称弗法)。
关于最短路径算法中的弗洛伊德算法：
# X5 e! P! E3 i/ {/ i* I" ]
我终于勉强理解了弗洛伊德算法(我简称弗法)。
! h# R# V6 Y+ G- Z
迪杰斯特拉算法我二十年前已知，最近才了解弗法，感到很难理解。利用抗战纪念日放假期间，闭关冥想弗法。
, N, L8 F; D$ F
我冥想出N步弗法，冥想出源码，但始终比网上源码多一重循环，为何网上源码是三重循环，我冥想者要在外面再套一层循环？这或许正是弗法精华乎？
& h0 `3 G5 B0 l; T& ]+ D
后来冥想悟道，此象星云假说，六王毕四海一，蜀山兀阿房出，或许正弗法精华乎？
8 Z- `/ y9 J* m5 {
弗法中，凡处理k点时，必连通所有关联k点之原始点与原始边乎！这点可能是关键！于是顿悟，大明江山！
4 i2 G8 ?6 Q$ G _7 R3 E% o! H( ^
9 ?3 E) z4 m6 A) S- J3 p
3 w) k1 v9 L& I5 h. h W
作者:
释永思
时间:
2015-9-6 13:41
现在专心思考弗洛伊德算法，这个可能要用到数学归纳法来证明的，百度网上没有人讲到用数归法
; Y$ K1 Q$ J% v
来证明弗法的。
7 h3 w; i( ]; f3 _' V9 M% ?# r$ H* q
作者:
qianlingwen
时间:
2015-9-10 14:37
我想我还是不明白
% B4 h* s9 [- o) ]# E
作者:
风靡全球
时间:
2015-9-10 17:54
加油
( H( f3 A" [0 N2 ^( t1 T8 _7 _
作者:
风靡全球
时间:
2015-9-10 17:54
加油
" I+ V- T7 ^+ W1 I3 P
作者:
风靡全球
时间:
2015-9-10 17:54
加油
$ r6 T5 P" ~& d7 f2 {
作者:
风靡全球
时间:
2015-9-10 17:54
加油
4 I) c4 h- W/ f$ ]# P
作者:
风靡全球
时间:
2015-9-10 17:55
加油
8 ~1 d& K! S8 h% g, K
作者:
风靡全球
时间:
2015-9-10 17:55
加油
( a4 E7 `1 U( z4 D8 |
作者:
风靡全球
时间:
2015-9-15 17:00
加油努力
7 X1 h0 Q a8 }! P
作者:
风靡全球
时间:
2015-9-16 18:00
加油 一定要努力哦
0 D- ~6 D. k; K+ C! o, l" L3 u
作者:
风靡全球
时间:
2015-9-16 18:00
加油 一定要努力哦
# T8 Y" r' w" D. G1 q
作者:
风靡全球
时间:
2015-9-16 18:00
加油 一定要努力哦
) b$ `* Z$ Z; M8 I( r y* ]
作者:
风靡全球
时间:
2015-9-16 18:01
加油 一定要努力哦
/ M6 K- Q. g6 C
作者:
风靡全球
时间:
2015-9-16 18:01
加油 一定要努力哦
( j" ~" x: S! |" ^6 w+ P9 U- r
作者:
风靡全球
时间:
2015-9-16 18:01
加油 一定要努力哦
/ R( f; y: L6 S1 ~4 _% @
作者:
风靡全球
时间:
2015-9-16 18:01
加油 一定要努力哦
7 u* r/ r% e" V3 q& ~& @8 Z
作者:
风靡全球
时间:
2015-9-16 18:01
加油 一定要努力哦
# s+ M! g/ X& L+ K" w+ V* Z
作者:
风靡全球
时间:
2015-9-16 18:01
加油 一定要努力哦
: s6 y8 L( Y. E+ O" o
作者:
风靡全球
时间:
2015-9-16 18:01
加油 一定要努力哦
4 ?/ Z/ `. t/ l4 j
作者:
释永思
时间:
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。 所以命题得证。
8 T/ j9 h& ~% Y# r$ q
作者:
zhwdiao
时间:
2015-9-24 09:02
加油，目前在看图论算法。
3 }' U {6 J; Y. I* X& ~- p" _
作者:
G天土生金
时间:
2019-7-20 11:07
加油 ,
- l! g& A2 A4 V# o: T w
欢迎光临 数学建模社区-数学中国 (http://www.madio.net/)
Powered by Discuz! X2.5