分枝限界法——单源最短路径 收藏

1,用set模拟优先级队列：

需要注意的是：在编写Node的“<”比较函数时，必须保证它是“严格弱小于”的，因为对set进行操作的函数如insert，find，erase等都是通过这个函数进行比较的，如果对两个键值都不能 判断它们的“<”关系，则认为它们相等。

view plaincopy to clipboardprint?
#include <iostream>
#include <set>
using namespace std;
const int N = 5;
const int E = 7;
const int MAX=65536;
int g[N][N];
int dis[N];
int pre[N];
struct Node
{
int id;
int len;
bool operator<(const Node &n)const//保证比较函数的严格若排序（如果两个键值，它们之间都不存在“小于关系”，则被视为相等）
{
if(len == n.len)
return id<n.id;
else
return len<n.len;
}
};
struct cmp
{
bool operator()(const Node &n1,const Node &n2)const
{
return n1<n2;
}
};
set<Node> mq;//模拟优先级队列（len越小优先级越大）
void branch_remove(int s)
{
dis[s]=0;
pre[s]=-1;

Node e;
e.id = s;
e.len = 0;
mq.insert(e);
int j = 0;
while(!mq.empty())
{
Node p = *(mq.begin());//取出最小值(优先级最高)
for(j=0;j<N;j++)
{
if(g[p.id][j]!=MAX && g[p.id][j]+p.len<dis[j])
{
dis[j] = g[p.id][j]+dis[p.id];
pre[j] = p.id;
Node t;
t.id = j;
t.len = dis[j];

//如果当前扩展点已经在队列里，修改其优先级，否则插入该扩展节点
mq.erase(t);
mq.insert(t);
}
}
//移除当前优先级最高的节点（作为活结点已经扩展完毕）
mq.erase(p);
}
}
int main()
{
int i=0;
int j =0;
int c=1;
for(i=0;i<N;i++)
for(j=0;j<N;j++)
if(i==j)
g[i][j] = 0;
else
g[i][j] = MAX;
for(i=0;i<N;i++)
dis[i]=MAX;
while(c<=E)
{
cin>>i;
cin>>j;
cin>>g[i][j];
c++;
}
branch_remove(0);
for(i=0;i<N;i++)
cout << dis[i]<<" ";
cout << endl;
}
#include <iostream>
#include <set>
using namespace std;
const int N = 5;
const int E = 7;
const int MAX=65536;
int g[N][N];
int dis[N];
int pre[N];
struct Node
{
int id;
int len;
bool operator<(const Node &n)const//保证比较函数的严格若排序（如果两个键值，它们之间都不存在“小于关系”，则被视为相等）
{
if(len == n.len)
return id<n.id;
else
return len<n.len;
}
};
struct cmp
{
bool operator()(const Node &n1,const Node &n2)const
{
return n1<n2;
}
};
set<Node> mq;//模拟优先级队列（len越小优先级越大）
void branch_remove(int s)
{
dis[s]=0;
pre[s]=-1;

Node e;
e.id = s;
e.len = 0;
mq.insert(e);
int j = 0;
while(!mq.empty())
{
Node p = *(mq.begin());//取出最小值(优先级最高)
for(j=0;j<N;j++)
{
if(g[p.id][j]!=MAX && g[p.id][j]+p.len<dis[j])
{
dis[j] = g[p.id][j]+dis[p.id];
pre[j] = p.id;
Node t;
t.id = j;
t.len = dis[j];

//如果当前扩展点已经在队列里，修改其优先级，否则插入该扩展节点
mq.erase(t);
mq.insert(t);
}
}
//移除当前优先级最高的节点（作为活结点已经扩展完毕）
mq.erase(p);
}
}
int main()
{
int i=0;
int j =0;
int c=1;
for(i=0;i<N;i++)
for(j=0;j<N;j++)
if(i==j)
g[i][j] = 0;
else
g[i][j] = MAX;
for(i=0;i<N;i++)
dis[i]=MAX;
while(c<=E)
{
cin>>i;
cin>>j;
cin>>g[i][j];
c++;
}
branch_remove(0);
for(i=0;i<N;i++)
cout << dis[i]<<" ";
cout << endl;
}

2，使用priority_queue

view plaincopy to clipboardprint?
#include <iostream>
#include <queue>
#include <functional>
using namespace std;
const int N = 5;
const int E = 7;
const int MAX=65536;
int g[N][N];
int dis[N];
int pre[N];
struct Node
{
int id;
int len;
bool operator<(const Node &n)const//保证比较函数的严格若排序（如果两个键值，它们之间都不存在“小于关系”，则被视为相等）
{
if(len == n.len)
return id<n.id;
else
return len<n.len;

}
};
struct cmp
{
bool operator()(const Node &n1,const Node &n2)const
{
return n1<n2;
}
};
priority_queue<Node,vector<Node>,cmp >mq;
void branch_remove(int s)
{
dis[s]=0;
pre[s]=-1;
Node e;
e.id = s;
e.len = dis[s];
mq.push(e);
int j = 0;
while(!mq.empty())
{
Node t = mq.top();
for(j=0;j<N;j++)
{
if(g[t.id][j]!=MAX && g[t.id][j]+t.len < dis[j])
{
dis[j] = g[t.id][j]+t.len;
pre[j] = t.id;
Node p;
p.id = j;
p.len = dis[j];
mq.push(p);
}
}
mq.pop();
}
}
int main()
{
int i=0;
int j =0;
int c=1;
for(i=0;i<N;i++)
for(j=0;j<N;j++)
if(i==j)
g[i][j] = 0;
else
g[i][j] = MAX;
for(i=0;i<N;i++)
dis[i]=MAX;
while(c<=E)
{
cin>>i;
cin>>j;
cin>>g[i][j];
c++;
}
branch_remove(0);
for(i=0;i<N;i++)
cout << dis[i]<<" ";
cout << endl;
}
#include <iostream>
#include <queue>
#include <functional>
using namespace std;
const int N = 5;
const int E = 7;
const int MAX=65536;
int g[N][N];
int dis[N];
int pre[N];
struct Node
{
int id;
int len;
bool operator<(const Node &n)const//保证比较函数的严格若排序（如果两个键值，它们之间都不存在“小于关系”，则被视为相等）
{
if(len == n.len)
return id<n.id;
else
return len<n.len;

}
};
struct cmp
{
bool operator()(const Node &n1,const Node &n2)const
{
return n1<n2;
}
};
priority_queue<Node,vector<Node>,cmp >mq;
void branch_remove(int s)
{
dis[s]=0;
pre[s]=-1;
Node e;
e.id = s;
e.len = dis[s];
mq.push(e);
int j = 0;
while(!mq.empty())
{
Node t = mq.top();
for(j=0;j<N;j++)
{
if(g[t.id][j]!=MAX && g[t.id][j]+t.len < dis[j])
{
dis[j] = g[t.id][j]+t.len;
pre[j] = t.id;
Node p;
p.id = j;
p.len = dis[j];
mq.push(p);
}
}
mq.pop();
}
}
int main()
{
int i=0;
int j =0;
int c=1;
for(i=0;i<N;i++)
for(j=0;j<N;j++)
if(i==j)
g[i][j] = 0;
else
g[i][j] = MAX;
for(i=0;i<N;i++)
dis[i]=MAX;
while(c<=E)
{
cin>>i;
cin>>j;
cin>>g[i][j];
c++;
}
branch_remove(0);
for(i=0;i<N;i++)
cout << dis[i]<<" ";
cout << endl;
}

二者的实现不同之处是：

使用set时，由于set能保证键值的唯一，所以在进行节点的扩展时，实际上是替换set中已存在节点的len值或者添加新节点。

而使用priority_queue不能保证键值唯一，且又不方便查找已存在节点（没有迭代器适配器等操作），故在进行节点扩展时，队列中可能存在重复键值节点，单它们的len值不同，这并不影响对本问题的求解，因为可以通过约束函数将len值较大的节点进行剪枝，但是在运用priority_queue求解其它问题时，这是应当注意的。

本文来自CSDN博客，转载请标明出处：http://blog.csdn.net/clearriver/archive/2009/08/30/4499739.aspx