数学建模社区-数学中国
标题:
我终于勉强理解了弗洛伊德算法(我简称弗法)。
[打印本页]
作者:
释永思
时间:
2015-9-5 08:57
标题:
我终于勉强理解了弗洛伊德算法(我简称弗法)。
关于最短路径算法中的弗洛伊德算法：
M: T# S6 p3 O( d2 e
我终于勉强理解了弗洛伊德算法(我简称弗法)。
: R8 d) i& X a4 r5 {0 I
迪杰斯特拉算法我二十年前已知，最近才了解弗法，感到很难理解。利用抗战纪念日放假期间，闭关冥想弗法。
1 \$ O$ g7 [( a2 r8 Y/ W
我冥想出N步弗法，冥想出源码，但始终比网上源码多一重循环，为何网上源码是三重循环，我冥想者要在外面再套一层循环？这或许正是弗法精华乎？
( q* c4 A( u9 i8 v* b
后来冥想悟道，此象星云假说，六王毕四海一，蜀山兀阿房出，或许正弗法精华乎？
3 D4 h' D! K" x
弗法中，凡处理k点时，必连通所有关联k点之原始点与原始边乎！这点可能是关键！于是顿悟，大明江山！
0 v; F/ O/ G# L. X& m" l& s3 [
3 Y. [- j0 l2 b0 c# r) U
# }+ p2 n* J/ ^* ?7 o( t6 }
作者:
释永思
时间:
2015-9-6 13:41
现在专心思考弗洛伊德算法，这个可能要用到数学归纳法来证明的，百度网上没有人讲到用数归法
, i9 X- u( Y* I# ^1 R$ R
来证明弗法的。
) |, M4 U5 a4 w0 J$ C4 G; q
作者:
qianlingwen
时间:
2015-9-10 14:37
我想我还是不明白
! D7 `8 _" ^3 w% m, J7 @4 t
作者:
风靡全球
时间:
2015-9-10 17:54
加油
, l: m4 ~& m! T! U- U
作者:
风靡全球
时间:
2015-9-10 17:54
加油
, s+ [0 l; Y( s% s; b$ L% w2 ?7 ?
作者:
风靡全球
时间:
2015-9-10 17:54
加油
" w k0 @! m$ r) w' l
作者:
风靡全球
时间:
2015-9-10 17:54
加油
+ ^/ H6 x8 K" p* e/ s: D8 P
作者:
风靡全球
时间:
2015-9-10 17:55
加油
9 H% E# e6 _/ g# Z
作者:
风靡全球
时间:
2015-9-10 17:55
加油
# h* K; `" I9 v; I& p$ m
作者:
风靡全球
时间:
2015-9-15 17:00
加油努力
8 w; C/ {3 B( X+ V' V6 \/ U3 h
作者:
风靡全球
时间:
2015-9-16 18:00
加油 一定要努力哦
- Q; p. D8 ^; y4 L3 e+ `- W
作者:
风靡全球
时间:
2015-9-16 18:00
加油 一定要努力哦
0 h; H; ^9 g0 F* F7 U
作者:
风靡全球
时间:
2015-9-16 18:00
加油 一定要努力哦
2 Z3 }/ X7 j7 t- {/ {
作者:
风靡全球
时间:
2015-9-16 18:01
加油 一定要努力哦
$ C4 U" H7 @/ c2 ^$ ?- _
作者:
风靡全球
时间:
2015-9-16 18:01
加油 一定要努力哦
) _4 M, q( P) S. v; m; i( _ R
作者:
风靡全球
时间:
2015-9-16 18:01
加油 一定要努力哦
. j0 Z; d5 {% z
作者:
风靡全球
时间:
2015-9-16 18:01
加油 一定要努力哦
; z/ P2 j! J, K5 V
作者:
风靡全球
时间:
2015-9-16 18:01
加油 一定要努力哦
: I/ V$ z0 |2 O$ F- V, c$ ^
作者:
风靡全球
时间:
2015-9-16 18:01
加油 一定要努力哦
0 ~+ H2 f6 o/ M( @+ u
作者:
风靡全球
时间:
2015-9-16 18:01
加油 一定要努力哦
+ X V% G( w6 h- F! r; |/ n, Y
作者:
释永思
时间:
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。 所以命题得证。
: c8 o+ R p; D; e
作者:
zhwdiao
时间:
2015-9-24 09:02
加油，目前在看图论算法。
1 ?; t6 t1 @3 R" O6 h2 `+ v
作者:
G天土生金
时间:
2019-7-20 11:07
加油 ,
- q4 p. p$ f# m8 ? Z
欢迎光临 数学建模社区-数学中国 (http://www.madio.net/)
Powered by Discuz! X2.5