数学建模社区-数学中国
标题:
我终于勉强理解了弗洛伊德算法(我简称弗法)。
[打印本页]
作者:
释永思
时间:
2015-9-5 08:57
标题:
我终于勉强理解了弗洛伊德算法(我简称弗法)。
关于最短路径算法中的弗洛伊德算法：
0 }+ v- k4 x# P' S
我终于勉强理解了弗洛伊德算法(我简称弗法)。
5 o# O5 m8 ^/ Z* x$ E
迪杰斯特拉算法我二十年前已知，最近才了解弗法，感到很难理解。利用抗战纪念日放假期间，闭关冥想弗法。
, ? v+ z; j1 M
我冥想出N步弗法，冥想出源码，但始终比网上源码多一重循环，为何网上源码是三重循环，我冥想者要在外面再套一层循环？这或许正是弗法精华乎？
* a3 f5 A' J# J' W
后来冥想悟道，此象星云假说，六王毕四海一，蜀山兀阿房出，或许正弗法精华乎？
- w0 x0 P% j4 r7 c& q
弗法中，凡处理k点时，必连通所有关联k点之原始点与原始边乎！这点可能是关键！于是顿悟，大明江山！
& S1 v- H* f5 K+ d, V# h, J' t, d. s" m
/ I; e& q+ J# q
" f* D' J1 y& ^3 [0 F2 I) w* L
作者:
释永思
时间:
2015-9-6 13:41
现在专心思考弗洛伊德算法，这个可能要用到数学归纳法来证明的，百度网上没有人讲到用数归法
* K3 f0 t2 _9 s/ C1 c
来证明弗法的。
5 \2 l, ~; \1 u) Y' f- K
作者:
qianlingwen
时间:
2015-9-10 14:37
我想我还是不明白
/ d& m e4 f9 R# [4 v" b
作者:
风靡全球
时间:
2015-9-10 17:54
加油
% v4 ?# B- J" l4 F/ t
作者:
风靡全球
时间:
2015-9-10 17:54
加油
( O$ G4 i* A, O! q$ G8 G
作者:
风靡全球
时间:
2015-9-10 17:54
加油
a5 J9 `' ?- _" }% J( O) w& L
作者:
风靡全球
时间:
2015-9-10 17:54
加油
& M) [: F' t8 o3 t' w; E
作者:
风靡全球
时间:
2015-9-10 17:55
加油
* O0 B& I# H |6 n: P6 d& z, Z
作者:
风靡全球
时间:
2015-9-10 17:55
加油
3 f5 R2 l5 {2 e6 q
作者:
风靡全球
时间:
2015-9-15 17:00
加油努力
5 z1 t3 _3 F6 J1 O5 m2 Q" D$ t
作者:
风靡全球
时间:
2015-9-16 18:00
加油 一定要努力哦
' H. r+ c$ F4 j2 @: }/ Q. Q
作者:
风靡全球
时间:
2015-9-16 18:00
加油 一定要努力哦
) \5 [* D) [4 q4 ?' j) H" s7 Q
作者:
风靡全球
时间:
2015-9-16 18:00
加油 一定要努力哦
7 O2 x/ I. F9 e) B5 o. B( y; G1 o
作者:
风靡全球
时间:
2015-9-16 18:01
加油 一定要努力哦
$ e8 {. |) ^3 I" i
作者:
风靡全球
时间:
2015-9-16 18:01
加油 一定要努力哦
) Y# {6 n- V2 {) m/ G
作者:
风靡全球
时间:
2015-9-16 18:01
加油 一定要努力哦
- b/ }; w9 c) N, B. K$ F
作者:
风靡全球
时间:
2015-9-16 18:01
加油 一定要努力哦
3 A3 G' h8 X3 n2 `
作者:
风靡全球
时间:
2015-9-16 18:01
加油 一定要努力哦
9 Y) W4 |" G5 t8 K$ H
作者:
风靡全球
时间:
2015-9-16 18:01
加油 一定要努力哦
+ u1 f) C3 a2 n. b; l2 t! q
作者:
风靡全球
时间:
2015-9-16 18:01
加油 一定要努力哦
3 o7 v& w! k$ z! ?
作者:
释永思
时间:
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。 所以命题得证。
- f" {9 Q4 T0 i4 p; `3 z
作者:
zhwdiao
时间:
2015-9-24 09:02
加油，目前在看图论算法。
! D& p2 [1 ]5 R% G5 e% _6 T7 `) O
作者:
G天土生金
时间:
2019-7-20 11:07
加油 ,
; A5 V% m1 g4 [6 A5 F3 a$ X
欢迎光临 数学建模社区-数学中国 (http://www.madio.net/)
Powered by Discuz! X2.5