Liny_@NotePad

沉迷ACG中

【模板】SPFA - 单源最短路径

YOYO posted @ 2008年12月07日 20:50 in 【算法】与【数据结构】 with tags SPFA 单源最短路径 , 2531 阅读

 看了wekooo给的某论文,从里面pascal翻过来 = =

  1. void SPFA(int s){
  2.     for(int i=1;i<=n;i++){
  3.         d[i] = MAX;
  4.     }
  5.         int queue[N*N] = {0};
  6.         bool visit[N] = {false};
  7.     int front = 0, rear = 1;
  8.         //int path[N];
  9.     queue[front] = s; visit[s] = true;  d[s] = 0;
  10.     while(front<rear){   
  11.         int u = queue[front];
  12.         visit[u] = false;
  13.         for(int i=1; i<=n; i++){
  14.             if (d[i]>d[u]+ edges[u][i]){
  15.                 d[i]= d[u]+edges[u][i];
  16.                 //path[i] = u;
  17.                 if( !visit[i] ){
  18.                     visit[i] = true;
  19.                     queue[rear++] = i;
  20.                 }
  21.             }
  22.                 }
  23.                 front++;
  24.     }
  25. }

调用时,初始结点s,目标结点e,则
SPFA(s);
cout<<d[e]<<endl;
即可。

注意结点是从1存储到N。
不能连通时值为MAX。


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter