a***n
发帖数: 404 | 1 求一个图中所有“两点最短距离”的方法？
有没有啥好的算法？ 如果用Dijkstra遍历代价太高了，而且有冗余。
有好的算法么？ |
l*****g
发帖数: 49 | 2 well studied problem, huge literature
google "all pairs shortest path" or "Floyd–Warshall algorithm"
or "Johnson's algorithm" or read an algorithms textbook ...
【在 a***n 的大作中提到】
: 求一个图中所有“两点最短距离”的方法？
: 有没有啥好的算法？ 如果用Dijkstra遍历代价太高了，而且有冗余。
: 有好的算法么？
|
a***n
发帖数: 404 | 3 JGraph 一直用的挺好的，可惜这些算法都没有实现，找了下，各种语言的都有，就是没
java的，郁闷死~~~
有开源代码么？ 看了几个比较有名的开源库，貌似没有找到合适的。
难道只能自己写。。。埃。 天天就干coding了。
【在 l*****g 的大作中提到】
: well studied problem, huge literature
: google "all pairs shortest path" or "Floyd–Warshall algorithm"
: or "Johnson's algorithm" or read an algorithms textbook ...
|
z*l
发帖数: 30 | 4 floyd 就5行
是没
【在 a***n 的大作中提到】
: JGraph 一直用的挺好的，可惜这些算法都没有实现，找了下，各种语言的都有，就是没
: java的，郁闷死~~~
: 有开源代码么？ 看了几个比较有名的开源库，貌似没有找到合适的。
: 难道只能自己写。。。埃。 天天就干coding了。
|
z*l
发帖数: 30 | 5 求准确解就是N^3
近似解不清楚。
for k = 1 to n do
for i = 1 to n do
for j = 1 to n do
if (dis[i,k]+dis[k,j]
dis[i,j] = dis[i,k]+dis[k,j];
这个太基础了
【在 a***n 的大作中提到】
: 求一个图中所有“两点最短距离”的方法？
: 有没有啥好的算法？ 如果用Dijkstra遍历代价太高了，而且有冗余。
: 有好的算法么？
|
a***n
发帖数: 404 | 6 这个Floyd 是n^3, 复杂度跟 类Dijkstra算法一样的，太高了。
不知道有没有稍微好一点的，看了Floyd-Warshall改进版好像也是差不多这个量级的。
没办法，图太大了。埃。。。
刚刚google了下，貌似 n^3很难突破，就 Johnson 稍微算最好了。。。
另外貌似我用的 《algorithm design》竟然没有提到 Johnson, 看来跟 Introduction
to algorithm 内容差别还是很大阿。。。
另外，如果已知要求的pair集合，貌似就很难决定哪种算法好了。因为很多算法都是
bottom-up的，这个对于求部分pair很不利阿。
【在 z*l 的大作中提到】
: 求准确解就是N^3
: 近似解不清楚。
: for k = 1 to n do
: for i = 1 to n do
: for j = 1 to n do
: if (dis[i,k]+dis[k,j]: dis[i,j] = dis[i,k]+dis[k,j];
: 这个太基础了
|
M**u
发帖数: 10158 | 7 取决于边可不可以<0啊
【在 a***n 的大作中提到】
: 求一个图中所有“两点最短距离”的方法？
: 有没有啥好的算法？ 如果用Dijkstra遍历代价太高了，而且有冗余。
: 有好的算法么？
|
t******t
发帖数: 51 | 8 The SIGMOD2008 best paper by Hanan Samet has something to do with your
problem. Check it out. |
c****r
发帖数: 185 | 9 Samet's paper only works on planar graphs.
It still needs to precompute distances of all pairs.
The good thing is that these distances can be stored in less than O(n^2)
space. |
