数学建模社区-数学中国
标题:
我终于勉强理解了弗洛伊德算法(我简称弗法)。
[打印本页]
作者:
释永思
时间:
2015-9-5 08:57
标题:
我终于勉强理解了弗洛伊德算法(我简称弗法)。
关于最短路径算法中的弗洛伊德算法：
: a5 G! y$ r6 n; y% j3 K
我终于勉强理解了弗洛伊德算法(我简称弗法)。
0 u. e8 z' E, U7 x8 G5 p+ O
迪杰斯特拉算法我二十年前已知，最近才了解弗法，感到很难理解。利用抗战纪念日放假期间，闭关冥想弗法。
) o) @) R* _1 H+ t8 V0 Z, h
我冥想出N步弗法，冥想出源码，但始终比网上源码多一重循环，为何网上源码是三重循环，我冥想者要在外面再套一层循环？这或许正是弗法精华乎？
4 L8 h% O0 V$ c- I+ N( P- L
后来冥想悟道，此象星云假说，六王毕四海一，蜀山兀阿房出，或许正弗法精华乎？
/ D3 h! t* D0 o, ^. z% g4 A- P& _
弗法中，凡处理k点时，必连通所有关联k点之原始点与原始边乎！这点可能是关键！于是顿悟，大明江山！
/ X S T) Q7 P3 C
- ~9 n) D! O. K$ c( x; k2 l
0 H- ~' L6 F/ H9 d# k3 C
作者:
释永思
时间:
2015-9-6 13:41
现在专心思考弗洛伊德算法，这个可能要用到数学归纳法来证明的，百度网上没有人讲到用数归法
; B; N! f: \9 E! }2 d# [0 m
来证明弗法的。
f, p5 G( B6 W9 ?
作者:
qianlingwen
时间:
2015-9-10 14:37
我想我还是不明白
) ?2 h+ S7 l9 V t$ K$ o, |
作者:
风靡全球
时间:
2015-9-10 17:54
加油
. t$ n# a' v" y0 [
作者:
风靡全球
时间:
2015-9-10 17:54
加油
# F+ C7 _2 w. A, I0 }+ _3 L
作者:
风靡全球
时间:
2015-9-10 17:54
加油
- w. e! { I+ |" |. d p2 x
作者:
风靡全球
时间:
2015-9-10 17:54
加油
4 C3 ]" n8 Y/ N# Q6 n* n
作者:
风靡全球
时间:
2015-9-10 17:55
加油
$ X( F; m' P; B# i: E
作者:
风靡全球
时间:
2015-9-10 17:55
加油
, R& f9 q X4 J
作者:
风靡全球
时间:
2015-9-15 17:00
加油努力
% z) b# Y ~6 L W1 ~/ N) ~# h, `
作者:
风靡全球
时间:
2015-9-16 18:00
加油 一定要努力哦
: [$ T9 ?8 [: W3 Y9 E; |1 g
作者:
风靡全球
时间:
2015-9-16 18:00
加油 一定要努力哦
/ K% D; c2 l/ o
作者:
风靡全球
时间:
2015-9-16 18:00
加油 一定要努力哦
! X0 l& {1 M U, G
作者:
风靡全球
时间:
2015-9-16 18:01
加油 一定要努力哦
' G( }) U9 S+ G9 l* W0 e+ Q- P; E5 ~
作者:
风靡全球
时间:
2015-9-16 18:01
加油 一定要努力哦
6 C: Y" c7 k- @/ P4 K2 B0 B
作者:
风靡全球
时间:
2015-9-16 18:01
加油 一定要努力哦
8 l2 s4 l& N& @# `- g
作者:
风靡全球
时间:
2015-9-16 18:01
加油 一定要努力哦
$ x1 a, d4 c1 ^7 ? j
作者:
风靡全球
时间:
2015-9-16 18:01
加油 一定要努力哦
) Q1 Z8 R0 `, n( b w
作者:
风靡全球
时间:
2015-9-16 18:01
加油 一定要努力哦
3 ~7 J. v( o5 s4 v( f! L
作者:
风靡全球
时间:
2015-9-16 18:01
加油 一定要努力哦
8 H- C* m" S# v
作者:
释永思
时间:
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 k- h P: J9 x6 ?. {
作者:
zhwdiao
时间:
2015-9-24 09:02
加油，目前在看图论算法。
; S! j. _6 D6 V2 I
作者:
G天土生金
时间:
2019-7-20 11:07
加油 ,
9 z5 V* \8 m9 j ^' ~5 g
欢迎光临 数学建模社区-数学中国 (http://www.madio.net/)
Powered by Discuz! X2.5