前向星+SPFA

Rainboy913 2013-12-07

展開全文

       這個算法，簡單的說就是隊列優(yōu)化的bellman-ford,利用了每個點不會更新次數(shù)太多的特點發(fā)明的此算法（僅為個人理解=.=）
      SPFA——Shortest Path Faster
      Algorithm，它可以在O(kE)的時間復(fù)雜度內(nèi)求出源點到其他所有點的最短路徑，可以處理負(fù)邊。SPFA的實現(xiàn)甚至比Dijkstra或者Bellman_Ford還要簡單：
      設(shè)Dist代表S到I點的當(dāng)前最短距離，F(xiàn)a代表S到I的當(dāng)前最短路徑中I點之前的一個點的編號。開始時Dist全部為+∞，只有Dist[S]=0，F(xiàn)a全部為0。
      維護一個隊列，里面存放所有需要進行迭代的點。初始時隊列中只有一個點S。用一個布爾數(shù)組記錄每個點是否處在隊列中。
      每次迭代，取出隊頭的點v，依次枚舉從v出發(fā)的邊v->u，設(shè)邊的長度為len，判斷Dist[v]+len是否小于Dist，若小于則改進Dist，將Fa記為v，并且由于S到u的最短距離變小了，有可能u可以改進其它的點，所以若u不在隊列中，就將它放入隊尾。這樣一直迭代下去直到隊列變空，也就是S到所有的最短距離都確定下來，結(jié)束算法。
      SPFA
      在形式上和寬度優(yōu)先搜索非常類似，不同的是寬度優(yōu)先搜索中一個點出了隊列就不可能重新進入隊列，但是SPFA中一個點可能在出隊列之后再次被放入隊列，也就是一個點改進過其它的點之后，過了一段時間可能本身被改進，于是再次用來改進其它的點，這樣反復(fù)迭代下去。設(shè)一個點用來作為迭代點對其它點進行改進的平均次數(shù)為k，有辦法證明對于通常的情況，k在2左右
      前向星優(yōu)化：
      不要把前向星想成什么高深莫測的東西……它其實就是一種鄰接表的緊縮存儲形式。
      為什么叫前向星？因為它是將邊按照前端點排序，并用一個數(shù)組k[i]記錄端點i第一次以左端點出現(xiàn)的位置。這樣，我們就能用O(E)的空間復(fù)雜度存儲下一個鄰接表，而避免了鏈表或N^2的龐大空間消耗。
      當(dāng)然，實際上我們并不需要排序：因為我們只需要知道某一條邊應(yīng)該放到什么位置即可。因而我們還需要一個數(shù)組t[i]存儲從i出發(fā)的邊的條數(shù)。則需要存儲在的位置就可以很輕易地求得。（詳見代碼）
      Butter題目代碼如下：
      Program butter(input,output);
      Type
         edge=record
                  x,y,d:longint;
              end;
      Var
         min,res,n,p,c,x,y,i,j,l,r:longint;
         te,e:array[0..3000] of edge;
         tk,t,k,num,d:array[1..800] of longint;
         q:array[1..100000] of longint;
         use:array[1..800] of boolean;
      Procedure swap(var n1,n2:longint);
      Var
         tmp:longint;
      Begin
         tmp:=n1;n1:=n2;n2:=tmp;
      End;
      Begin
         assign(input,'butter.in');reset(input);
         readln(n,p,c);
         for i:=1 to n do
         begin
            read(x);
            inc(num[x]);
         end;
         for i:=1 to c do
         begin
            with e[i*2-1] do readln(x,y,d);
            e[i*2]:=e[i*2-1];
            swap(e[i*2].x,e[i*2].y);
         end;
         c:=c*2;
         for i:=1 to c do inc(t[e[i].x]);
         j:=0;k[1]:=1;
         for i:=2 to p do
            k[i]:=k[i-1]+t[i-1];
         tk:=k;te:=e;
         for i:=1 to c do
         begin
            e[tk[te[i].x]]:=te[i];
            inc(tk[te[i].x]);
         end;
         min:=maxlongint;
         for i:=1 to p do
         begin
            fillchar(q,sizeof(q),0);
            fillchar(d,sizeof(d),127);
            fillchar(use,sizeof(use),false);
            q[1]:=i;l:=1;r:=1;d[i]:=0;use[i]:=true;
            repeat
                  for j:=k[q[l]] to k[q[l]]+t[q[l]]-1 do
                     if d[q[l]]+e[j].d<d[e[j].y] then
                     begin
                        d[e[j].y]:=d[q[l]]+e[j].d;
                        if not use[e[j].y] then
                        begin
                           use[e[j].y]:=true;
                           inc(r);
                           q[r]:=e[j].y;
                        end;
                     end;
                  use[q[l]]:=false;
                  inc(l);
            until l>r;
            res:=0;
            for j:=1 to p do
               res:=res+d[j]*num[j];
            if res<min then min:=res;
         end;
         assign(output,'butter.out');rewrite(output);
         writeln(min);close(output);
      End.