推 jim055006:感謝精銳拜占庭聖騎兵的詳細解答..我現在完全了解了... 10/20 21:39
※ 引述《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)這句是甚麼意思??
v.d : upper bound on the weight of a shortest path from source s to v
v.π : v's predecessor
INITIALIZE-SINGLE-SOURCE(G,s)
for each vertex v∈G.V
v.d = ∞
v.π= NIL
s.d = 0
: 第二 題目中提到的multiple edge是甚麼意思??
: 第三 有沒有高手可以大心的Demo一下這個Algo.....XD
打上來太累了 翻一下課本吧 這些課本都有
: 第四 念DS念了那麼久，我發現我不知道甚麼是linear time = ="
: 高手們方便解釋一下嗎??
: 以上是我滿滿的疑問.....
: 希望大家幫我解惑一下
: 鋼溫!!!!!!
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 123.195.196.47
※ 編輯: Byzantin 來自: 123.195.196.47 (10/20 10:30)