[問題] DAG找最短路徑問題

[VeranoDB (StarNighT)]

最近友人問我一個演算法的考題

找了很多資料還是不太會想請教大大們

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)
→ suhorng:第一個空格應該跟拓樸順序有關
→ suhorng:第二, 三個空格就是 relax, 比較短就放鬆
推 singlovesong:topological sorted order, d[vi]+arc(vi,vj) <d[vj]
→ singlovesong:d[vj] = d[vi] + arc(vi,vj)
→ singlovesong:猜的
→ VeranoDB:感謝回答