算法(2)-欧几得米试探法-类Dijkstra算法"/>
源点-汇点最短路径快速算法(2)-欧几得米试探法-类Dijkstra算法
1、欧几米得网络中的源点-汇点最短路径问题即:解决任2点之间的最短路径问题。欧几米得网络也是对称的:边具有双向性 ,将无向加权欧几米得图解决成加权有向图时,能马上得到此网络。 2、这些网络满足以下两条重要性质 1)距离满足三角不等式:s->d的距离<=(s->x的距离)+(x->d的距离) 2)顶点位置给出了路径长度的下限:从s到d的路径>=s到d的距离 3、在查找从源点S到汇点D的一条路径时,遇到了第三个顶点V,可知道,我们不仅要通过已经发现的从S到V的路径,而且下一步从V到D的 最佳行进方式(只是最理想的情况)为: 首先走边V-W,然后找到一条长度等于W到D之间的直线距离的路径 4、使用以下改进后的标准算法, 1)使用以下3个量的和做为每条边V-W的权重(即WT[W])=(S到V的已知路径长度)+(边V-W权重)+(从W到T的距离) 2)优先级定义为以下函数(dist为返回两个顶点间距离的函数),该优先级也就是WT[T->V]: ( wt[v]-dist(v,d)) + t->wt + dist(t->v,d) 注意:由1)可知:(wt[v]-dist(v,d))为从S->V的最短路径长度 3)C代码如下(使用类Dijkstra算法的标准DFS实现): 5、通过优先级方式和Dijkstra算法来解决,称这种运算方法为欧几得米试探法, 6、试探法揭示的几何性: 1)如果从S到D的最短路径是Z,则算法检查的顶点大致位于 一个椭圆内,这个椭圆由 点X的轨迹定义,在此椭圆上,从S到 X的距离加上从 X到D的距离先于Z。对于典型的欧几米得图,这个椭圆内的顶点期望数少于 以Z为半径、以源点为圆心的圆内顶点数更多推荐
源点-汇点最短路径快速算法(2)-欧几得米试探法-类Dijkstra算法
发布评论