[問題] DAG找最短路徑問題
最近友人問我一個演算法的考題
找了很多資料還是不太會想請教大大們
Let G be a direct acyclic graph with vertex set V and arc set E. Suppose that
s is the only vertwx with in-degree zero. Consider following for finding the
shorest path lengths from s to all the other vertices. Here each arc has unit
length.
Algorithm TTT
find a (__) (v1=s,v2,...,vn) of G // What kind of sequence it is
set d[1]=0 and d[i]=n for any i>1;
for i from 1 to n-1 do
for each j such that there is an arc (vi,vj) do
if (__) then (__)
the time complexity is O(__)
問這4個填空
我只有找到是最後一個好像是O(|V|+|E|)
不知道可不可以在這問，如果不行我會刪除
感謝!
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 1.168.102.152
※ 編輯: VeranoDB 來自: 1.168.102.152 (02/03 18:31)
→
02/03 20:32, , 1F
02/03 20:32, 1F
→
02/03 20:32, , 2F
02/03 20:32, 2F
推
02/03 23:08, , 3F
02/03 23:08, 3F
→
02/03 23:08, , 4F
02/03 23:08, 4F
→
02/03 23:08, , 5F
02/03 23:08, 5F
→
02/07 00:15, , 6F
02/07 00:15, 6F