最短路

最短路的问题的各种算法都是以BFS的思想为基础,最开始的普通的入口-出口迷宫游戏也可以看作是一种最短路问题,只是在这个问题里面,每次行动的步长一样,都是1;而最短路问题里面常处理的是步长(路径长度)不一样的问题。

常用算法

最短路问题有四个常用的算法,Bellman_ford、Dijkstra、floyd和spfa;其中,dijkstran算法又可以用堆优化。

Bellman-Ford 算法

介绍
  • 找出起点S到其他所有可达点的最短距离
  • 可用来判断是否有起点S可达的负圈

在大循环内遍历边,只要该边的起点的最短距离已知晓(目前已知的最短,有可能被更新,即只要不是inf就行),那么该边的终点的最短距离则是当前点的最短距离或者是该边的起点的最短距离加上边的权值。
d[e.to] = min(d[e.to], d[e.from] + e.cost) .

代码
struct edge{
int from,to;
int cost;
};
edge es[maxe];
int d[maxv]; //最短距离
int V,E;

void bellman_ford(int s){
for(int i=0;i<V;i++){
d[i]=inf;
}
d[s]=0;
while(true){
bool update = false;
for(int i=0;i<E;i++){
edge e = es[i];
if(d[e.from] != inf && d[e.to]>d[e.from]+e.cost){
d[e.from] = d[e.to] + e.cost;
upate = true;
}
}
if(!upate)
break;
}
}

Dijkstra 算法

介绍
  • 找出起点S到其他所有可达点的最短距离
  • 图中存在负边,该算法就无法正确求解问题

Dijkstra算法是针对bellman_ford算法进行操作上的优化得到的。

  1. 找到最短距离已经确定的顶点,从它出发更新相邻顶点的最短距离。
  2. 此后不需要再关心 1 中的“最短距离已经确定的顶点 ”。
代码
int cost[maxv][maxv];
int d[maxv];
bool used[maxv];
int V;
void dijkstra(int s){
memset(d,inf,sizeof(d));
memset(used,false,sizeof(used));
d[s] = 0;
while(true){
int v = -1;
for(int u=0;u<V;u++){
if(!used[u] && (v==-1 || d[u] < d[v]))
v = u;
}
if(v==-1)
break;
used[v] = true;
for(int i=0;i<V;i++){
d[i] = min(d[i], d[v] + cost[v][i]);
}
}
}
堆优化

每次把确定了最短距离的点同它的最短距离一起放进优先级队列里面。

struct edge {
int to;
int cost;
};
typedef pair<int, int>p; //first是最短距离,second是顶点的编号
vector<edge> G[max_v];
int d[max_v];
int V; //顶点数
struct cmp {
bool operator()(p a,p b) {
if (a.first < b.first)
return a < b;
return a > b;
}
};

void dijkstra(int s) {
priority_queue<p, vector<p>,cmp> que;
fill(d, d + V,INF);
d[s] = 0;
que.push(p(0, s));
//初始化

while (!que.empty()) {
p P = que.top();
que.pop();
int v = P.second;
if (d[v] < P.first)
continue;
for (int u = 0; u < G[v].size(); u++) {
edge e = G[v][u];
if (d[e.to] > d[v] + e.cost) {
d[e.to] = d[v] + e.cost;
que.push(p(d[e.cost], d[e.to]));//wrong
}
}
}
}

floyd 算法

介绍
  • 可以处理是负边的情况
  • 寻找任意两点间的最短距离

判断图中是否有负圈,只需检查是否存在d[i][i]是负数的顶点i就可以了

代码
void floyd(){
for(int k=0;k<V;k++){
for(int i=0;i<V;i++){
for(int j=0;j<V;j++){
d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
}
}
}
}

spfa 算法

介绍
  • 可以处理负边权
  • 有顶点入队了要记得标记vis数组,有顶点出队了记得消除那个标记
  • 如果某个点进入队列的次数超过N次则存在负环(SPFA无法处理带负环的图)
  • SPFA的两种写法,bfs和dfs,bfs判别负环不稳定,dfs的话判断负环很快
代码
int spfa_bfs(int s)  
{
queue <int> q;
memset(d,0x3f,sizeof(d));
d[s]=0;
memset(c,0,sizeof(c));
memset(vis,0,sizeof(vis));

q.push(s); vis[s]=1; c[s]=1;
//顶点入队vis要做标记,另外要统计顶点的入队次数
int OK=1;
while(!q.empty())
{
int x;
x=q.front(); q.pop(); vis[x]=0;
//队头元素出队,并且消除标记
for(int k=f[x]; k!=0; k=nnext[k]) //遍历顶点x的邻接表
{
int y=v[k];
if( d[x]+w[k] < d[y])
{
d[y]=d[x]+w[k]; //松弛
if(!vis[y]) //顶点y不在队内
{
vis[y]=1; //标记
c[y]++; //统计次数
q.push(y); //入队
if(c[y]>NN) //超过入队次数上限,说明有负环
return OK=0;
}
}
}
}

return OK;

}
int spfa_dfs(int u)  
{
vis[u]=1;
for(int k=f[u]; k!=0; k=e[k].next)
{
int v=e[k].v,w=e[k].w;
if( d[u]+w < d[v] )
{
d[v]=d[u]+w;
if(!vis[v])
{
if(spfa_dfs(v))
return 1;
}
else
return 1;
}
}
vis[u]=0;
return 0;
}

例题

  • poj1062 枚举+dijkstra.
  • poj1860 正圈
  • poj3259 负圈
  • poj3660 传递闭包