«

[算法导论笔记]单源最短路径

最短路径估计和前驱结点的初始化
INITIALIZE-SINGLE-SOURCE(G, s)  
  for each vertex v∈G.V   
      v.d = ∞  
      v.π = NIL  
  s.d = 0  
松弛操作
RELAX(u, v, w)  
  if v.d > u.d + w(u, v)  
      v.d = u.d + w(u, v)  
      v.π = u  
Bellman-Ford算法
BELLMAN-FORD(G, w, s)  
  for i=1 to |G.V|-1  
      for each edge(u, v)∈G.E  
          RELAX(u, v, w)  
  for each edge(u, v)∈G.E  
      if v.d > u.d + w(u, v)  
          return FALSE  
  return TRUE  
有向无环图的单源最短路径算法
DAG-SHORTEST-PATHS(G, w, s)  
  topologically sort the vertices of G  
  INITIALIZE-SINGLE-SOURCE(G, s)  
  for each vertex u, taken in topologically sorted order  
      for each vertex v∈G.Adj[u]  
          RELAX(u, v, w)  
Dijkstra算法
DIJKSTRA(G, w, s)  
  INITIALIZE-SINGLE-SOURCE(G, s)  
  S = Empty  
  Q = G.V  
  while Q ≠ Empty  
      u = EXTRACT-MIN(Q)  
      S = S ∪ {u}  
      for each vertex v∈G.Adj[u]  
          RELAX(u, v, w)  
分享