[理工] [DS] single source shortest path

[jim055006 (jim)]

題目如下:

We have a directed graph G=(V,E) represented using adjacency list.
The edge costs are integers in the range {1,2,3,4,5}. Assume that
G has no self-loops or mutiple edges. Design an algorithm that
solves the single-source shortest path problem in G in O(|V|+|E|).


答案為:

DAG-Shortest-Path(G,w,s)
  {
   Topologically sort V[G]

   Initialize-Single-Source(G,s)

   For each u taken in topological order do

        for each v€adj[u] do
          {
           if d[v]>d[u]+w(u,v) then

              d[v]=d[u]+w(u,v)
          }
   }


我的疑問:

第一  答案的Algo中的Initialize-Single-Source(G,s)這句是甚麼意思??

第二  題目中提到的multiple edge是甚麼意思??

第三  有沒有高手可以大心的Demo一下這個Algo.....XD

第四  念DS念了那麼久，我發現我不知道甚麼是linear time = ="
      高手們方便解釋一下嗎??

以上是我滿滿的疑問.....
希望大家幫我解惑一下
鋼溫!!!!!!

--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 223.139.247.27
推 genius945:這邊忘光了...不過2應該是多重邊,就是點與點之間不只一
→ genius945:個邊     4的話,O(n)就是linear的,用來表示time complex
→ genius945:ity就是linear time囉
→ jim055006:還是很感謝天才的解答...
推 FRAXIS:這解法有問題吧 Topological Sort未必存在..