利用分支限界法求解单源最短路(Dijkstra)问题

分支限界法定义:采用Best fist search算法,并使用剪枝函数的算法称为分支界限法。

分支限界法解释:按Best first的原则,有选择的在其child中进行扩展,从而舍弃不含有最优解的分支,不断重复这一过程,直到找到答案或者判定无解。

分支界限法常常用到优先队列来选择最佳扩展节点,有时也会用到普通队列,以先进先出为原则来进行筛选。

单源最短路问题定义:给定有向图和起点,寻找到达所有点的最短路径。

单源最短路的分支限界法概述:首先把节点加入优先队列,以到当前节点的最短路为下界,之后不断地从队列中取出最优扩展点,观察其可抵达的所有目标节点。

若当前消耗大于等于全局上界及目标节点消耗,则放弃该节点。所示代码因没有规定终点,即每个点都要输出最小路径,则不检查这一步。

若当前路径消耗+两节点间路径消耗<目标节点目前最小消耗(即更新后下界<目标当前下界)
则用不等式左边的和替换掉右边的值,并将该目标节点加入优先队列。

循环这个过程直到队列为空,即可获得图中所有节点的最短路。

代码如下:

#include <queue>
#include <vector> const int MAX_V = ;//最大顶点数
const int INF = ;//正无穷
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] = ;
while (!pq.empty())
{
int tmp = pq.top();pq.pop();
for (int i = ;i < V;++i)
{
if (d[i] > d[tmp] + cost[tmp][i])
{
d[i] = d[tmp] + cost[tmp][i];
pq.push(i);
}
}
}
}
上一篇:牛客编程巅峰赛S1第6场 - 黄金&钻石&王者 C.星球游戏 (单源最短路,Dijkstra)


下一篇:ListView的深入学习