源点－汇点最短路径快速算法（2）－欧几得米试探法－类Dijkstra算法

算法（2）－欧几得米试探法－类Dijkstra算法"/>

源点－汇点最短路径快速算法（2）－欧几得米试探法－类Dijkstra算法

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