数学建模社区-数学中国
标题:
我终于勉强理解了弗洛伊德算法(我简称弗法)。
[打印本页]
作者:
释永思
时间:
2015-9-5 08:57
标题:
我终于勉强理解了弗洛伊德算法(我简称弗法)。
关于最短路径算法中的弗洛伊德算法：
5 q( C$ q+ K: r$ |1 u$ R% W( U
我终于勉强理解了弗洛伊德算法(我简称弗法)。
3 M o4 w. }3 K! B6 z
迪杰斯特拉算法我二十年前已知，最近才了解弗法，感到很难理解。利用抗战纪念日放假期间，闭关冥想弗法。
3 O) B5 B5 c. H1 X/ H
我冥想出N步弗法，冥想出源码，但始终比网上源码多一重循环，为何网上源码是三重循环，我冥想者要在外面再套一层循环？这或许正是弗法精华乎？
" ` A' k* z7 l! {# \7 ^
后来冥想悟道，此象星云假说，六王毕四海一，蜀山兀阿房出，或许正弗法精华乎？
$ C$ w+ j D; O' @( q$ C! [
弗法中，凡处理k点时，必连通所有关联k点之原始点与原始边乎！这点可能是关键！于是顿悟，大明江山！
. U) ^, i: ^# i0 X
8 T8 q" r, b6 R% m5 M |* \
2 x! q' w. M9 h \6 ]5 W3 b4 }
作者:
释永思
时间:
2015-9-6 13:41
现在专心思考弗洛伊德算法，这个可能要用到数学归纳法来证明的，百度网上没有人讲到用数归法
! ]5 a: o' ]9 Y. t+ o; Z2 `
来证明弗法的。
0 x8 _: o3 q% F; |8 K9 I! J4 F
作者:
qianlingwen
时间:
2015-9-10 14:37
我想我还是不明白
2 E$ E$ L/ a! X/ H7 T/ K
作者:
风靡全球
时间:
2015-9-10 17:54
加油
7 p5 U: O- G& K
作者:
风靡全球
时间:
2015-9-10 17:54
加油
) M% @; h3 G! R$ z8 Z$ v
作者:
风靡全球
时间:
2015-9-10 17:54
加油
- _( g6 \# b& L8 O+ L! Y
作者:
风靡全球
时间:
2015-9-10 17:54
加油
7 Y! o5 D) o, u3 A/ S
作者:
风靡全球
时间:
2015-9-10 17:55
加油
! }( M5 |" N( G$ u
作者:
风靡全球
时间:
2015-9-10 17:55
加油
& U, O9 h- _: y7 M" ~, R
作者:
风靡全球
时间:
2015-9-15 17:00
加油努力
: | F, a3 o- ]; {* W
作者:
风靡全球
时间:
2015-9-16 18:00
加油 一定要努力哦
" A/ R+ a1 W1 \) J/ Q4 o* E+ h
作者:
风靡全球
时间:
2015-9-16 18:00
加油 一定要努力哦
; v4 f: ]" r3 i2 J1 r& l% l
作者:
风靡全球
时间:
2015-9-16 18:00
加油 一定要努力哦
1 r# H7 g/ f3 j S8 ^
作者:
风靡全球
时间:
2015-9-16 18:01
加油 一定要努力哦
9 W. k0 s; F4 |: P1 T' ^: }
作者:
风靡全球
时间:
2015-9-16 18:01
加油 一定要努力哦
9 |1 s1 y) I, s6 D1 g5 p
作者:
风靡全球
时间:
2015-9-16 18:01
加油 一定要努力哦
9 ?1 V; {6 B% u$ ~" e# l% w
作者:
风靡全球
时间:
2015-9-16 18:01
加油 一定要努力哦
. a# d. n% p0 A6 {
作者:
风靡全球
时间:
2015-9-16 18:01
加油 一定要努力哦
2 b* C' a8 p8 r! K; r
作者:
风靡全球
时间:
2015-9-16 18:01
加油 一定要努力哦
3 C" o9 w% ]# C* Q3 r
作者:
风靡全球
时间:
2015-9-16 18:01
加油 一定要努力哦
: n' ?, _' h- i6 r
作者:
释永思
时间:
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。 所以命题得证。
' j5 j0 `3 R0 d5 g3 P
作者:
zhwdiao
时间:
2015-9-24 09:02
加油，目前在看图论算法。
9 Q: o- N; l% h( Q5 g# Z
作者:
G天土生金
时间:
2019-7-20 11:07
加油 ,
! D) W s& C& D# Z9 R& D ]# t
欢迎光临 数学建模社区-数学中国 (http://www.madio.net/)
Powered by Discuz! X2.5