Single-Source Shortest Path in Directed Acyclic Graphs

在dag中，儘管edge有負值，
但絕對不會有negative-weight cycle，
所以一定可以找到每個點的最短路徑。

首先要使用topology sort去排序Graph的每個點，
接著從左到右，算出與該node相鄰點的距離。
在source左邊的node全都是∞，
也就是不用算該node與其他node的距離。

Introduction to Algorithms Fig. 24.5

(a)
一開始的Graph，
除了source為0以外，
其他點都初始化為∞。
接下來從左到右，
依序計算每個點到其他點的距離。


(b)
r在source左邊，因此跳過不算。
r塗黑代表計算完成。


(c)
從s出發的out edge連接到t,x，
因此重新計算t,x的值：
t = s + (s,t) = 0+2 = 2
x = s + (s,x) = 0+6 = 6
把t,x的parent更新為s，
接著s塗黑代表計算完成。





(d)
從t出發的out edge連接到x,y,z，
因此重新計算x,y,z的值：
x = t + (t,x) = 2+7 = 9  --> 因為9大於原本的6，因此不更新
y = t + (t,y) = 2+4 = 6
z = t + (t,z) = 2+2 = 4
x的parent維持不動，
把y,z的parent更新為t，
接著把t塗黑代表計算完成。

(e)~(g)依此類推，
圖(g)為最後計算的結果，
每個node裡填的值代表從source出發到該node的最短路徑，
灰色的edge表示parent。