数学建模社区-数学中国
标题:
我终于勉强理解了弗洛伊德算法(我简称弗法)。
[打印本页]
作者:
释永思
时间:
2015-9-5 08:57
标题:
我终于勉强理解了弗洛伊德算法(我简称弗法)。
关于最短路径算法中的弗洛伊德算法：
1 q6 r/ t4 o; |* _( S
我终于勉强理解了弗洛伊德算法(我简称弗法)。
: ^9 ~) I# f; {
迪杰斯特拉算法我二十年前已知，最近才了解弗法，感到很难理解。利用抗战纪念日放假期间，闭关冥想弗法。
. L6 a7 j- d) T
我冥想出N步弗法，冥想出源码，但始终比网上源码多一重循环，为何网上源码是三重循环，我冥想者要在外面再套一层循环？这或许正是弗法精华乎？
$ e1 s( ~2 z, L+ D# n
后来冥想悟道，此象星云假说，六王毕四海一，蜀山兀阿房出，或许正弗法精华乎？
( G' P" F/ U3 k' m5 y; u0 Y2 Y6 C
弗法中，凡处理k点时，必连通所有关联k点之原始点与原始边乎！这点可能是关键！于是顿悟，大明江山！
) N9 X: J6 a! N$ }
( y4 H) f5 D- s" u
5 K, J3 P0 z% O: }) g) o* R
作者:
释永思
时间:
2015-9-6 13:41
现在专心思考弗洛伊德算法，这个可能要用到数学归纳法来证明的，百度网上没有人讲到用数归法
0 j1 `; b' s9 S( [
来证明弗法的。
8 n- |6 u8 K) p3 n; ]5 a
作者:
qianlingwen
时间:
2015-9-10 14:37
我想我还是不明白
& q0 J7 x1 W, r! t3 }
作者:
风靡全球
时间:
2015-9-10 17:54
加油
0 }8 A4 _+ z0 x
作者:
风靡全球
时间:
2015-9-10 17:54
加油
; \: D5 h& l5 Z }
作者:
风靡全球
时间:
2015-9-10 17:54
加油
3 T: C) b W: i
作者:
风靡全球
时间:
2015-9-10 17:54
加油
1 ~+ n, E/ G2 p
作者:
风靡全球
时间:
2015-9-10 17:55
加油
% b( i8 }) x$ l, B" F" ?' Y( ]
作者:
风靡全球
时间:
2015-9-10 17:55
加油
7 X5 |/ E; U3 _4 p( n3 t
作者:
风靡全球
时间:
2015-9-15 17:00
加油努力
- @2 s$ ?1 M2 P$ q" n! s
作者:
风靡全球
时间:
2015-9-16 18:00
加油 一定要努力哦
/ Z/ ?, v% B" E1 C$ _( i7 {5 S
作者:
风靡全球
时间:
2015-9-16 18:00
加油 一定要努力哦
2 n5 a; l( e/ W% `% u6 i3 B
作者:
风靡全球
时间:
2015-9-16 18:00
加油 一定要努力哦
/ h" K6 ]1 g& d* p5 ]& i
作者:
风靡全球
时间:
2015-9-16 18:01
加油 一定要努力哦
$ I; { l9 n" A0 [
作者:
风靡全球
时间:
2015-9-16 18:01
加油 一定要努力哦
5 @4 S F( W" s" g" N$ v8 z
作者:
风靡全球
时间:
2015-9-16 18:01
加油 一定要努力哦
; a5 c# r: x6 a8 C" @4 j0 K
作者:
风靡全球
时间:
2015-9-16 18:01
加油 一定要努力哦
6 Z& e* r1 y$ G: o- A8 J
作者:
风靡全球
时间:
2015-9-16 18:01
加油 一定要努力哦
6 _' h) i' @0 B& O! ^, ~& i
作者:
风靡全球
时间:
2015-9-16 18:01
加油 一定要努力哦
1 e8 X5 u d$ _+ ~7 W
作者:
风靡全球
时间:
2015-9-16 18:01
加油 一定要努力哦
2 _; [( Y% V9 _6 S+ d' W
作者:
释永思
时间:
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。 所以命题得证。
) A" K9 F. i1 r6 l( J8 O* |
作者:
zhwdiao
时间:
2015-9-24 09:02
加油，目前在看图论算法。
! t0 b( h! P8 F7 ~
作者:
G天土生金
时间:
2019-7-20 11:07
加油 ,
5 P0 s# I3 H8 ^3 m" E( @9 N& B
欢迎光临 数学建模社区-数学中国 (http://www.madio.net/)
Powered by Discuz! X2.5