---
# System prepended metadata

title: bellman-ford
tags: [garph]

---

---
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)
從某點發一個訊號 經多久使所有節點收到訊號