分支限界法之单源最短路径

问题描述

  下面以一个例子来说明单源最短路径问题：在下图所给的有向图G中，每一边都有一个非负边权。要求图G的从源顶点s到所有其他顶点的最短路径。

算法思想

  解单源最短路径问题的优先队列式分支限界法用一极小堆来存储活结点表。其优先级是结点所对应的当前路长。

（1）从图G的源顶点s和空优先队列开始。

（2）结点s成为扩展节点，它的儿子结点被依次插入堆中。

（3）从堆中取出具有最小当前路长的结点作为当前扩展结点，并依次检查与当前扩展结点相邻的所有顶点。

（4）如从当前扩展结点i到顶点j有边可达，且从源出发，途经顶点i再到顶点j的路径的长度小于当前已得到的s到j的最优路径长度，则将该顶点作为活结点插入到活结点优先队列中。

（5)这个结点的扩展过程一直继续到活结点优先队列为空时为止。

算法中，利用结点间的控制关系进行剪枝。从源顶点s出发，2条不同路径到达图G的同一顶点。由于两条路径的路长不同，因此可以将路长长的路径所对应的树中的结点为根的子树剪去

//当前扩展结点E ，内含顶点编号E.i, //C[n][n]是距离矩阵，dest[j]是当前到达j顶点的最短距离。 while (true){for (int j = 1; j <= n; j++)if ((c[E.i][j]<inf)&&(E.length+c[E.i][j]<dist[j])) {// 顶点i到顶点j可达，且满足控制约束dist[j]=E.length+c[E.i][j];//prev[j]值便是J的前驱顶点号，是为构造解而设prev[j]=E.i; // 加入活结点优先队列MinHeapNode<Type> N;N.i=j;N.length=dist[j];H.Insert(N);}// 取下一扩展结点try {H.DeleteMin(E);} // 优先队列空 catch (OutOfBounds) {break;} }