斑的家

這是用來解shortest path 的演算法.

作法大概是一直更新

if d(j) > d(i) + Cij then

  d(j) = d(i) + Cij

因為不知道要選哪個基礎點i 來做比較好, 所以就是不斷嘗試

時間複雜度O(nm) n 為點個數, m 為邊數

d[s] = 0

d(j) = INFINITE for j in N not s

LIST={s}

while ( LIST not empty )

{

 remove an element i from LIST -------------------- (1)

 for each edge(i,j)

   if( d[j] > d[i] + Cij)

   {

          d[j] = d[i]+Cij;

          if j not in LIST then add j to LIST

         # else move j to the front of LISt ---------------(2)

   }

}

在(1), 如果每次都拿最前面的element 則稱為FIFO label correcting algorithm

在(2), 如果執行它的話, 就稱為dequeue implementation

執行2 的原因在於, 如果j  更新的話, j 又在shortest path 上中間的位置, 則在j 的後面的點就至少等到j 來更新它們.

不過這個想法不完全對, 但是有書說, 這樣的作法在sparse graph上, 很有用.