作者VeranoDB (StarNighT)
看板Prob_Solve
标题[问题] DAG找最短路径问题
时间Sun Feb 3 18:30:06 2013
最近友人问我一个演算法的考题
找了很多资料还是不太会想请教大大们
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)
1F：→ suhorng:第一个空格应该跟拓朴顺序有关 02/03 20:32
2F：→ suhorng:第二, 三个空格就是 relax, 比较短就放松 02/03 20:32
3F：推 singlovesong:topological sorted order, d[vi]+arc(vi,vj) <d[vj] 02/03 23:08
4F：→ singlovesong:d[vj] = d[vi] + arc(vi,vj) 02/03 23:08
5F：→ singlovesong:猜的 02/03 23:08
6F：→ VeranoDB:感谢回答 02/07 00:15