[图论] SPFA求最短路

SPFA求最短路需要借助一个队列来实现，每轮松弛时将在队列中的点直接更改距离，不在队列中的点入队同时更改距离

思路
[cc lang=”C++”]
起点入队
while(队列不为空){
队首为v
for(与v相连的节点e){
if(松弛成功){
if(e不在队列中)
e入队
更改距离
}
}
}
[/cc]

需要用到的变量

[cc lang=”C++”]

struct Edge{
    int v;
    int d;
};

bool used[MAXN]; //是否在队内
int dis[MAXN]; //距离

vector <Edge> map[MAXN]; //储存图

int que[MAXN * 200]; //模拟队列
int Front,Tail; //模拟队列
int n,m;

[/cc]

实现代码
[cc lang=”C++”]
void spfa(int k){

    dis[1] = 0; 
    Front = 0;
    que[Tail++] = 1; //起点进队
    used[1] = true;

    while(Front < Tail){
        int x = que[Front++];
        used[x] = false;

        for(register int i=0;i<map[x].size();i++){
            if(dis[x] + map[x][i].d < dis[map[x][i].v]){ //松弛操作
                if(!used[map[x][i].v]){
                    used[map[x][i].v] = true; //不在队内，入队
                    que[Tail++] = map[x][i].v; 
                }
                dis[map[x][i].v] = dis[x] + map[x][i].d; //距离
            }
        }
    }

}

[/cc]

BLOG