bellman-ford

圖的儲存
圖的深度優先遍歷

鄰接
出邊
度 入邊

bellman-ford

單源最短路徑問題(SSSP問題)

1-2-3-4
正序
(1,2,2)
(2,3,-1)
(3,4,3)
只需一輪

(3,4,3)
(2,3,-1)
(1,2,2)
反序
n-1輪
每次需等上一輪更新完 最外層那輪不需更新

(x,y,z)
y>x+z
y = x+z

dist[y] > dist[x] + z
比dist[y]小就更新
先假定無窮大去逼近
得最小解
反證法

z小於無窮大 不斷替代去逼近

743 網路延遲時間
1-n node
有向邊的傳遞時間
times[i] = (u,v,w)
從某點發一個訊號 經多久使所有節點收到訊號