--- tags: garph --- # bellman-ford ```javascript= ``` 圖的儲存 圖的深度優先遍歷 鄰接 出邊 度 入邊 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) 從某點發一個訊號 經多久使所有節點收到訊號