•按照队列先进先出（FIFO） 原则选取下一个节点为扩展 节点。
•按照优先队列中规定的优先 级选取优先级最高的节点成 为当前扩展节点。
给定带权有向图G =(V,E)，其中 每条边的权是非负实数。另外， 还给定V中的一个顶点，称为源。 现在要计算从源到所有其它各顶 点的最短路长度。这里路的长度 是指路上各边权之和。这个问题 通常称为单源最短路径问题。
在算法扩展结点的过程中，一旦 发现一个结点的下界不小于当前 找到的最短路长，则算法剪去以 该结点为根的子树。
在算法中，利用结点间的控制关 系进行剪枝。从源顶点s出发，2 条不同路径到达图G的同一顶点。 由于两条路径的路长不同，因此 可以将路长长的路径所对应的树 中的结点为根的子树剪去。
算法从源节点S开始S
a
b
c
计算当前最短路程为
2
3
4
6走bgmr，bgmp路
u
ed
gf
h
径。当前最短路径为 7，扩展得aeko.当前 5 最短路径为8.算法结
49
5
12
6
qk
ml
束
57
6 10
r
p
12
88
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])
•分支限界法常以广度优先或以最小耗费（最大效益）优先的方式搜索问题的
1
解空间树。
•在分支限界法中，每一个活结点只有一次机会成为扩展结点。活结点一旦成
2
为扩展结点，就一次性产生其所有儿子结点。在这些儿子结点中，导致不可
行解或导致非最优解的儿子结点被舍弃，其余儿子结点被加入活结点表中
3
•此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过 程。这个过程一直持续到找到所需的解或活结点表为空时为止。
被扩展，3个子节点被
插入堆中计算当前最
短路径为2将当前路径
最短的节点扩展，即
走au,ae,ad计算当前最
短路径为3，将其扩展，
走 bg,bf 计 算 当 前 最 短
路径为4，由先进先出
原则，走ch.
5
s
a
b
c
2
3
4
u ed g
f
h
4
95
12 6
单源路径问题的解空间树 节点旁数字为当前路长
s
当前最短路程为4，将其
else enode = (HeapNode) heap.removeMin();
}
总结：
分支限界法，通过目标函数和约束条件减少无效 操作，尽早发现剪枝点。适用于解决满足约束条 件的解中找出是目标函数值达到最大或最小的解。
所以单源最短路径很适合用分支限界法解决~~
使用优先队列式分支限界法，用一极小堆来存储活结点表。其优 先级是结点所对应的当前路长，当前路长小的节点优先
算法从图G的源顶点s和空优先队列开始。结点s被扩展后，它 的儿子结点被依次插入堆中。此后，算法从堆中取出具有最 小当前路长的结点作为当前扩展结点，并依次检查与当前扩 展结点相邻的所有顶点。如果从当前扩展结点i到顶点j有边可 达，且从源出发，途经顶点i再到顶点j的所相应的路径的长度 小于当前最优路径长度，则将该顶点作为活结点插入到活结 点优先队列中。这个结点的扩展过程一直继续到活结点优先 队列为空时为止。
扩 展 即 走 aeq,aek; 计 算 最短路程为5，注意：当 前结点不小于已找到的 最短路程，剪枝：不再
a 2
u ed
b
3
g
f
c 4
h
扩展继续，最短路程为5， 5
4 95
12
6
将 其 扩 展 ， 即 bgm,bgl ； 计算最短路 径为 5.满足
q k10
计算当前最短路程6， 满足剪枝条件，剪枝
{ // 顶点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;