上一節我們寫了Bellman-Ford算法解決負權邊的問題：
http://blog.csdn.net/wtyvhreal/article/details/43450727
當談到對Bellman-Ford算法的優化時，我們提出了兩種優化方案，其中第一種已經給出了解決方案，那麼第二種優化方案：
優化二：
在每次松弛後，會有一些頂點已經求得了最短路，此後這些頂點的最短路估計值就會一直保持不變，不再受後續松弛的影響，但是每次還要判斷是否需要松弛，這裡浪費了時間，是以
需要：每次僅對最短路徑估計值發生變化了的頂點的所有出邊執行松弛操作。
鄰接表存儲圖：
n個頂點，m條邊。
數組實作鄰接表。對每一條邊進行1-m編号。用u，v，w三個數組來記錄每條邊的資訊，即u[i],v[i],w[i]表示第i條邊是從第 u[i]号頂點到v[i]号頂點且權值為w[i].
first數組的1-n号單元格分别用來存儲1-n号頂點的第一條邊的編号，初始的時候因為沒有邊加入所有都是-1.即first[u[i]]儲存頂點u[i]的第一條邊的編号，next[i]存儲“編号為i的邊”的“下一條邊”的編号。
接下來周遊邊。周遊1号訂單的每一條邊。
在找到1号頂點的第一條邊之後，剩下得邊都可以在next數組中一次找到
此時周遊某個頂點的邊的時候的周遊順序正好與讀入時候的順序相反。因為在為每個頂點插入邊的時候都是直接插入“連結清單”的首部而不是尾部。
用臨接表來存儲圖的時間空間複雜度是O(M)，周遊每一條邊的時間複雜度也是O(M)，如果一個圖是稀疏圖的話，M要遠小于N^2，是以稀疏圖選用鄰接表來存儲比用鄰接矩陣來存儲好很多。
Bellman-Ford的隊列優化
上一篇中我們提到的Bellman-Ford算法的第二種優化：每次僅對最短路徑發生變化了的點的相鄰邊執行松弛操作。
每次選取隊首頂點u，對頂點u的所有出邊進行松弛操作。例如有一條u->v的邊，如果通過u->v這條邊使得源點到頂點v的最短路徑變短，且頂點v不在目前的隊列中，将頂點v放入隊尾。（但是一個點可以出去以後，再次入隊列）。在對頂點u的所有出邊松弛完畢後，将頂點u出隊。接下來不斷從隊列中取出新的隊首頂點在進行如上操作，直至隊列空為止。
代碼實作，用鄰接表存儲這個圖：
運作結果：
使用隊列優化的Bellman-Ford算法的時間複雜度在最壞的情況下也是O(NM).通過隊列優化的Bellman-Ford中，如果某個點進入隊列的次數超過n次，那麼這個圖則肯定存在負環。