【模板】SPFA - 单源最短路径
看了wekooo给的某论文，从里面pascal翻过来 = =
-
void SPFA(int s){
-
for(int i=1;i<=n;i++){
-
d[i] = MAX;
-
}
-
int queue[N*N] = {0};
-
bool visit[N] = {false};
-
int front = 0, rear = 1;
-
//int path[N];
-
queue[front] = s; visit[s] = true; d[s] = 0;
-
while(front<rear){
-
int u = queue[front];
-
visit[u] = false;
-
for(int i=1; i<=n; i++){
-
if (d[i]>d[u]+ edges[u][i]){
-
d[i]= d[u]+edges[u][i];
-
//path[i] = u;
-
if( !visit[i] ){
-
visit[i] = true;
-
queue[rear++] = i;
-
}
-
}
-
}
-
front++;
-
}
-
}
调用时，初始结点s，目标结点e，则
SPFA(s);
cout<<d[e]<<endl;
即可。
注意结点是从1存储到N。
不能连通时值为MAX。
评论 (0)
