最短路徑問題

最短路徑問題的抽象

*在網絡中，求兩個不同頂點之間的所有路徑中，邊的權值之和最小的那一條路徑。

這條路徑就是兩點之間的最短路徑（shortest path）

第一個頂點為源點（source）

最後一個頂點為終點（destination）

問題分類

單源最短路徑問題：從某固定源點出發，求其到所有其他頂點的最短路徑。

       （有向）無權圖

       （有向）有權圖

多源最短路徑問題：求任意兩頂點間的最短路徑

無權圖的單源最短路徑算法

按照遞增（非遞減）的順序找出到各個頂點的最短路。

void Unweighted ( Vertex S ) 
{ Enqueue(S, Q);
  while(!IsEmpty(Q)){
    V = Dequeue(Q); 
    for ( V 的每個鄰接點 W )
      if ( dist[W] == -1  ) {
        dist[W] = dist[V]+1;
        path[W] = V;
        Enqueue(W, Q);
      }
  }
}
           

時間複雜度：T=O(V+E)

有權圖的單源最短路算法

按照遞增的順序找出到各個頂點的最短路

Dijkstra算法

dist[w]=min{dist[w],dist[v]+<v,w>的權重}
           

僞代碼實作：

void Dijkstra( Vertex s )
{ while (1) {
    V = 未收錄頂點中dist最小者;
    if ( 這樣的V不存在 )
      break; 
    collected[V] = true;
    for ( V 的每個鄰接點 W )
      if ( collected[W] == false ) 
    if ( dist[V]+E<V,W> < dist[W] ) {
         dist[W] = dist[V] + E<V,W> ;
         path[W] = V;
    }
  }
}
           

推薦資料： Dijkstra算法

多源最短路算法

Floyd算法

推薦檢視此部落格：

最短路徑Floyd算法