数学建模社区-数学中国
标题:
我终于勉强理解了弗洛伊德算法(我简称弗法)。
[打印本页]
作者:
释永思
时间:
2015-9-5 08:57
标题:
我终于勉强理解了弗洛伊德算法(我简称弗法)。
关于最短路径算法中的弗洛伊德算法：
0 R9 R8 g/ ?5 U4 ?/ V# Z, k( t, R
我终于勉强理解了弗洛伊德算法(我简称弗法)。
! X' t! u* Q1 J4 A) I
迪杰斯特拉算法我二十年前已知，最近才了解弗法，感到很难理解。利用抗战纪念日放假期间，闭关冥想弗法。
; S( x0 `8 k% u# {
我冥想出N步弗法，冥想出源码，但始终比网上源码多一重循环，为何网上源码是三重循环，我冥想者要在外面再套一层循环？这或许正是弗法精华乎？
0 ]" O+ u7 C8 A
后来冥想悟道，此象星云假说，六王毕四海一，蜀山兀阿房出，或许正弗法精华乎？
8 u9 X! l! S: C
弗法中，凡处理k点时，必连通所有关联k点之原始点与原始边乎！这点可能是关键！于是顿悟，大明江山！
& V! t* j7 E* s* p5 D7 v. j9 W
7 Z3 ]+ Z2 B9 A& s& S. A( c: b: {
- m+ F, I) z# l1 x6 h0 E. ]! O8 j5 t
作者:
释永思
时间:
2015-9-6 13:41
现在专心思考弗洛伊德算法，这个可能要用到数学归纳法来证明的，百度网上没有人讲到用数归法
: o: t( o# `* s- y% v7 [
来证明弗法的。
- v4 C. H; \3 |( U) ^' ?
作者:
qianlingwen
时间:
2015-9-10 14:37
我想我还是不明白
; R! D' ?$ m& H# [
作者:
风靡全球
时间:
2015-9-10 17:54
加油
# u7 L% P. }2 X' N) C
作者:
风靡全球
时间:
2015-9-10 17:54
加油
7 U9 } {# Q& G$ N* l
作者:
风靡全球
时间:
2015-9-10 17:54
加油
# g% v/ Y- J0 i- Z; C4 _9 V; j
作者:
风靡全球
时间:
2015-9-10 17:54
加油
7 C3 _, m+ \ p3 Y4 ^, _8 {
作者:
风靡全球
时间:
2015-9-10 17:55
加油
* {- p7 L( w8 K5 _' p1 B5 z
作者:
风靡全球
时间:
2015-9-10 17:55
加油
# S% h' D# R7 B1 L
作者:
风靡全球
时间:
2015-9-15 17:00
加油努力
6 Q* N4 D) T& t5 R( j( {9 }( p
作者:
风靡全球
时间:
2015-9-16 18:00
加油 一定要努力哦
5 k+ d- t# j4 o1 w
作者:
风靡全球
时间:
2015-9-16 18:00
加油 一定要努力哦
8 \2 p( ^: C4 F3 a7 ~
作者:
风靡全球
时间:
2015-9-16 18:00
加油 一定要努力哦
# U9 J9 x, _* [8 m: W4 d
作者:
风靡全球
时间:
2015-9-16 18:01
加油 一定要努力哦
& g0 ~" n! {1 j4 ~' t
作者:
风靡全球
时间:
2015-9-16 18:01
加油 一定要努力哦
% \! O. Q; N* C; t/ E9 A( p0 c
作者:
风靡全球
时间:
2015-9-16 18:01
加油 一定要努力哦
1 F& I& ?7 i" T4 B3 Q# ]$ X/ p
作者:
风靡全球
时间:
2015-9-16 18:01
加油 一定要努力哦
4 w7 V- Z: m1 C( y: x* _" t
作者:
风靡全球
时间:
2015-9-16 18:01
加油 一定要努力哦
( s1 C) P9 S" c, I3 `
作者:
风靡全球
时间:
2015-9-16 18:01
加油 一定要努力哦
* M4 f R8 }* m/ }4 m
作者:
风靡全球
时间:
2015-9-16 18:01
加油 一定要努力哦
! p4 Z4 J4 y% 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。 所以命题得证。
/ C3 @# ]0 e0 A6 i
作者:
zhwdiao
时间:
2015-9-24 09:02
加油，目前在看图论算法。
+ B, V- Q$ S8 v8 p1 U& [/ w% ?
作者:
G天土生金
时间:
2019-7-20 11:07
加油 ,
$ o/ ?* c$ e2 P0 Y/ y
欢迎光临 数学建模社区-数学中国 (http://www.madio.net/)
Powered by Discuz! X2.5