That?s not just logic. That?s really sensilbe.
re: Bellman-Ford算法 infinity 2008-11-14 21:43
@新手
bellman-ford的優化是通過隊列實現的，也就是通常所說的spfa(Shortest Path Faster Algorithm)
具體操作方法是建一個隊列queue[]，用一個數組dist[]表示各點到起點的距離，用一個數組vis[]表示某點是否在隊列里面，然后循以下步驟：
1：將起點入隊列。
2：取隊首元素u，對u的每一鄰接點v實施松弛操作：即如果dist[u]+w[u][v]<dist[v](能被更新)，則dist[v]＝dist[u]+w[u][v]，如果v不再隊列中，就將點v入隊列。
３：如果隊列空則算法結束，否則繼續2一直到隊列空為止。
時間復雜度大概是O(ke)， 其中k為所有頂點進隊的平均次數，k一般小于等于2。
還有就是，有時候有些題，不用隊列而用棧可能會更快！