摘要：
分枝定界法的定义：使用Bestfirstsearch算法和修剪函数的算法称为分枝定界法。分支定界法的解释：根据最佳优先原则，有选择地在其子级中展开，从而丢弃没有最优解的分支，并重复该过程，直到找到答案或没有确定解。单源最短路径问题的定义：给定有向图和起点，找到所有点的最短路径。单源最短路径的分支定界方法概述：首先将节点添加到优先级队列中，将到当前节点的最短路径作为下限，然后从队列中连续获取最佳扩展点，以观察它可以到达的所有目标节点。
分支限界法定义：采用Best fist search算法，并使用剪枝函数的算法称为分支界限法。
分支限界法解释：按Best first的原则，有选择的在其child中进行扩展，从而舍弃不含有最优解的分支，不断重复这一过程，直到找到答案或者判定无解。
分支界限法常常用到优先队列来选择最佳扩展节点，有时也会用到普通队列，以先进先出为原则来进行筛选。
单源最短路问题定义：给定有向图和起点，寻找到达所有点的最短路径。
单源最短路的分支限界法概述：首先把节点加入优先队列，以到当前节点的最短路为下界，之后不断地从队列中取出最优扩展点，观察其可抵达的所有目标节点。
若当前消耗大于等于全局上界及目标节点消耗，则放弃该节点。所示代码因没有规定终点，即每个点都要输出最小路径，则不检查这一步。
若当前路径消耗+两节点间路径消耗<目标节点目前最小消耗（即更新后下界<目标当前下界）
则用不等式左边的和替换掉右边的值，并将该目标节点加入优先队列。
循环这个过程直到队列为空，即可获得图中所有节点的最短路。
代码如下：
#include <queue> #include <vector> const int MAX_V = 100;//最大顶点数 const int INF = 100000;//正无穷 int cost[MAX_V][MAX_V];//节点间cost表（即图） int d[MAX_V], V, s;//起点到各个顶点的距离，顶点数，起点 //自定义优先队列less比较函数 struct cmp { bool operator()(int &a, int &b) const { //因为优先出列为greater，所以反向定义实现最小值优先 return d[a] > d[b]; } }; void Dijkstra() { std::priority_queue<int, std::vector<int>, cmp> pq; pq.push(s); d[s] = 0; while (!pq.empty()) { int tmp = pq.top();pq.pop(); for (int i = 0;i < V;++i) { if (d[i] > d[tmp] + cost[tmp][i]) { d[i] = d[tmp] + cost[tmp][i]; pq.push(i); } } } }