Bellman Algo

MurkyPig
翛然野叟
Published in
1 min readFeb 18, 2019

Relaxation

After relaxation

雖然Bellman可以允許負邊,但是當下列情況,則無法解出來

因為5+3-10 = -2,無法解出來,但是可以偵測出是否有負環

。shortest path 有 |v|-1個邊,做成所有|v|-1的路徑樹,一共有|v|-1層

。時間複雜度O((V+E)*V) →O(V*E)

--

--