清华大学出版社 TSINGHUA UNIVERSITY PRESS 62单源最短路径问题 1.问题描述 下面以一个例子来说明单源最短路径问题:在下图所给的有 向图G中,每一边都有一个非负边权。要求图G的从源顶点到目 标顶点t之间的最短路径。 d f k h
6 6.2 单源最短路径问题 1. 问题描述 下面以一个例子来说明单源最短路径问题：在下图所给的有 向图G中，每一边都有一个非负边权。要求图G的从源顶点s到目 标顶点t之间的最短路径
清华大学出版社 TSINGHUA UNIVERSITY PRESS 62单源最短路径问题 下图是用优先队列式分支限界法解有向图G的单源最短路径问题 产生的解空间树。其中,每个结点旁边的数字表示该结点所对应 的当前路长 4 9○ ○12 ○6 i8 k 705 14 108
7 6.2 单源最短路径问题 下图是用优先队列式分支限界法解有向图G的单源最短路径问题 产生的解空间树。其中，每一个结点旁边的数字表示该结点所对应 的当前路长
清华大学出版社 TSINGHUA UNIVERSITY PRESS 62单源最短路径问题 2.算法思想 解单源最短路径问题的优先队列式分支限界法用一极小堆来存 储活结点表。其优先级是结点所对应的当前路长。 算法从图G的源顶点s和空优先队列开始。结点s被扩展后,它的 U子结点被依次插入堆中。此后,算法从堆中取出具有最小当前 路长的结点作为当前扩展结点,并依次检查与当前扩展结点相邻 的所有顶点。如果从当前扩展结点倒顶点有边可达,且从源出 发,途经顶点再到顶忘的所相应的路径的长度小于当前最优路 径长度,则将该页点作为活结点插入到活结点优先队列中。这个 结点的扩展过程一直继续到活结点优先队列为空时为止
8 6.2 单源最短路径问题 2. 算法思想 解单源最短路径问题的优先队列式分支限界法用一极小堆来存 储活结点表。其优先级是结点所对应的当前路长。 算法从图G的源顶点s和空优先队列开始。结点s被扩展后，它的 儿子结点被依次插入堆中。此后，算法从堆中取出具有最小当前 路长的结点作为当前扩展结点，并依次检查与当前扩展结点相邻 的所有顶点。如果从当前扩展结点i到顶点j有边可达，且从源出 发，途经顶点i再到顶点j的所相应的路径的长度小于当前最优路 径长度，则将该顶点作为活结点插入到活结点优先队列中。这个 结点的扩展过程一直继续到活结点优先队列为空时为止
清华大学出版社 TSINGHUA UNIVERSITY PRESS 62单源最短路径问题 3.剪枝策略 在算法扩展结点的过程中,一旦发现一个结点的下界不小于 当前找到的最短路长,则算法剪去以该结点为根的子树。 在算法中,利用结点间的控制关系进行剪枝。从源顶点s出发 2条不同路径到达图G的同一顶点。由于两条路径的路长不同,因 此可以将路长长的路径所对应的树中的结点为根的子树剪去
9 6.2 单源最短路径问题 3. 剪枝策略 在算法扩展结点的过程中，一旦发现一个结点的下界不小于 当前找到的最短路长，则算法剪去以该结点为根的子树。 在算法中，利用结点间的控制关系进行剪枝。从源顶点s出发， 2条不同路径到达图G的同一顶点。由于两条路径的路长不同，因 此可以将路长长的路径所对应的树中的结点为根的子树剪去
清华大学出版社 TSINGHUA UNIVERSITY PRESS 62单源最短路径问题 while(true ∥搜索问题的解空间 for(int j=1; j<=n: j++) f(a[enode ij[ Float MAX VALUE & enode length+[. i[l distLD ∥顶点到顶点j可达,且满足控制约束 disti=enode. length+a[enode iLl 顶点利和间有边,且此路 plilFenode. 1; 径长小于原先从原点到 的路径长 HeapNode node new HeapNode(j, distiL heap. put(node);∥加入活结点优先队列 if (heap is Empty) break; else enode =(HeapNode) heap. removeMinO
10 6.2 单源最短路径问题 while (true) { // 搜索问题的解空间 for (int j=1;j<=n;j++) if(a[enode.i][j] < Float.MAX_VALUE && enode.length+a[enode.i][j] < dist[j]) { // 顶点i到顶点j可达，且满足控制约束 dist[j]=enode.length+a[enode.i][j]; p[j]=enode.i; HeapNode node = new HeapNode(j,dist[j]); heap.put(node); // 加入活结点优先队列 } if (heap.isEmpty()) break; else enode = (HeapNode) heap.removeMin(); } 顶点I和j间有边，且此路 径长小于原先从原点到j 的路径长