«

[算法导论笔记]所有结点对的最短路径问题

基于矩阵乘法的动态规划算法求解所有最短路径
EXTEND_SHORTEST_PATHS(L, W)  
  n = L.rows  
  let L' = l'(i,j) be a new n*n matrix  
  for i=1 to n  
      for j=1 to n  
          l'(i,j) = ∞  
  return L'  

SLOW-ALL-PATHS-SHORTEST-PATHS(W)  
  n = W.rows  
  L[1] = W  
  for m=2 to n-1  
      let L[m] be a new n*n matrix  
      L[m] = EXTEND_SHORTEST_PATHS(L(m-1), W)  
  return L[n-1]  
使用重复平方技术来计算上述矩阵序列
FASTER-ALL-PAIRS-SHORTEST-PATHS(W)  
  n = W.rows  
  L[1] = W  
  m = 1  
  while m<n-1  
      let L[2m] be a new n*n matrix  
      L[2m] = EXTEND_SHORTEST_PATHS(L[m], L[m])  
      m = 2m  
  return L[m]  
Floyd-Warshall算法(佛洛依德算法)
FLOYD-WARSHALL(W)  
  n = W.rows  
  D[0] = W  
  for k=1 to n  
      let D[k] = d[k](i,j) be a new n*n matrix  
   for i=1 to n  
      for j=1 to n  
          d[k](i,j) = min(d[k-1](i,j), d[k-1](i,k)+d[k-1](k,j))  
  return D[n]  
有向图的传递闭包算法
TRANSITIVE-CLOSURE(G)  
  n = G.V  
  let T[0] = {t[0](i,j)} be a new n*n matrix  
  for i=1 to n  
      for j=1 to n  
          if i==j or (i,j)∈G.E  
              t[0](i,j) = 1  
          else  t[0](i,j) = 0  
  for k=1 to n  
      let T[k] = {t[k](i,j)} be a new n*n matrix  
      for i=1 to n  
          for j=1 to n  
              t[k](i,j) = t[k-1](i,j) ∨ (t[k-1](i,k)∧t[k-1](k,j))  
  return T[n]  
用于稀疏图的Johnson算法
JOHNSON(G, w)  
  compute G', where G'.V = G.V∪{s},  
      G'.E = G.V∪{(s,v):v∈G.V}, and  
      w(s,v)=0 for all v∈G.V  
  if BELLMAN-FORD(G', w, s) == FALSE  
      print"the input graph contain a negative-weigh cycle"  
  else  for each vertex v∈G'.V  
          set h(v) to the value if δ(s,v)  
              computed by the Bellman-Ford algorithm  
        for each edge(u,v)∈G'.E  
            w'(u,v) = w(u,v) + h(u) + h(v)  
        let D={d(u,v)} be a new n*n matrix  
        for each vertex u∈G'.V  
            run DIJKSTRA(G,w',u) to compute δ'(u,v) for all δ∈G.V  
            for each vertex v∈G.V  
                d(u,v) = δ'(u,v) + h(v) - h(u)  
  return D  
分享