作者netsphere (再一次重来...)
看板Prob_Solve
标题Re: [问题] Floyd演算法的一个题目
时间Mon Aug 4 21:26:41 2008
※ 引述《netsphere (再一次重来...)》之铭言：
: ※ 引述《netsphere (再一次重来...)》之铭言：
: : 有点懒的算~ 叫程式帮你算吧 http://rafb.net/p/zgvUbv26.html
: : 其实我也有个问题要问 >///<
: : 递回式: distk(i,j)=Min(distk-1(i,j),distk-1(i, k)+distk-1(k, j))
: : 直接用递回式定义来写是 O(n^4) 我的程式就是.....
: : 为什麽可以压到O(n^3) 是那里偷吃步了?
: 不懂怎麽证明.....Orz
: 先说一下 我对Dn的定义 Dn是表从i走n步到j的最短距离的矩阵Mij
: 後来想了一下能压到 O(n^3) 是因为直接建立 Dn-1 的矩阵
: 偷吃了建立 D1 D2 ....Dn-2 的时间
: 如果一般人照观念写出来应该都是O(n^4) XD
我重看了一次 Floyd-Warshall algorithm 原来我从观念上就错了 ......Orz
不过往好处想 我发明了 Netsphere All-Pairs Shortest Path algorithm for (N^4) XD
谢谢参与讨论的各位 Orz
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 122.118.84.152