作者：July、sunbaigui。二零一一年三月二十五日。
出處：http://blog.csdn.net/v_JULY_v。
------------------
前言：
本人不喜歡寫諸如“如何學算法”此類的文章，一來怕被人認為是自以為是，二來話題太泛，怕扯得太遠，反而不著邊際。所以，一直不打算寫怎麼學習算法此類的文章。
不過，鑒於讀者的熱心支持與關注，給出以下幾點小小的建議，僅供參考：
1、算法，浩如煙海，找到自己感興趣的那個分支，或那個點來學習，然後，一往無前的深入探究下去。
2、興趣第一，一切，由著你的興趣走，忌浮躁。
3、思維敏捷。給你一道常見的題目，你的頭腦中應該立刻能冒出解決這道問題的最適用的數據結構，以及算法。
4、隨興趣，多刷題。ACM題。poj，面試題，包括下文將出現的研究生復試上機考試題，都可以作為你的編程練習題庫。
5、多實踐，多思考。學任何一個算法，反復研究，反復思考，反復實現。
6、數據結構是一切的基石。不必太過專注於算法，一切算法的實現，原理都是依托數據結構來實現的。弄懂了一個數據結構，你也就通了一大片算法。
7、學算法，重優化。
8、學習算法的高明之處不在於某個算法運用得有多自如，而在於通曉一個算法的內部原理，運作機制，及其來龍去脈。
ok，話不再多。希望，對你有用。
接下來，咱們來通過最近幾年的浙大研究生復試上機試題，來學習或鞏固常用的算法。
浙大研究生復試2010年上機試題-最短路徑問題
問題描述：
給你n個點，m條無向邊，每條邊都有長度d和花費p，給你起點s終點t，要求輸出起點到終點的最短距離及其花費，如果最短距離有多條路線，則輸出花費最少的。
輸入：輸入n,m，點的編號是1~n,然後是m行，每行4個數 a,b,d,p，表示a和b之間有一條邊，且其長度為d，花費為p。最後一行是兩個數 s,t;起點s，終點t。n和m為0時輸入結束。
(1<n<=1000, 0<m<100000, s != t)
輸出：一行有兩個數， 最短距離及其花費。（下文，會詳細解決）
幾個最短路徑算法的比較
ok，怎麼解決上述的最短路徑問題列?提到最短路徑問題，想必大家會立馬想到Dijkstra 算法，但Dijkstra 算法的效率如何列?
我們知道，Dijkstra 算法的運行時間，依賴於其最小優先隊列的采取何種具體實現決定，而最小優先隊列可有以下三種實現方法：
1、利用從1至|V| 編好號的頂點，簡單地將每一個d[v]存入一個數組中對應的第v項，
如上述DIJKSTRA（G，w，s）所示，Dijkstra 算法的運行時間為O(V^2+E)。
2、如果是二叉/項堆實現最小優先隊列的話，EXTRACT-MIN(Q)的運行時間為O(V*lgV)，
所以，Dijkstra 算法的運行時間為O(V*lgV+E*lgV)，
若所有頂點都是從源點可達的話，O（(V+E)*lgV）=O（E*lgV）。
當是稀疏圖時，則E=O(V^2/lgV)，此Dijkstra 算法的運行時間為O(V^2)。
3、采用斐波那契堆實現最小優先隊列的話，EXTRACT-MIN(Q)的運行時間為O(V*lgV)，
所以，此Dijkstra 算法的運行時間即為O(V*lgV+E)。
綜上所述，此最小優先隊列的三種實現方法比較如下：
EXTRACT-MIN + RELAX
I、 簡單方式： O（V*V + E*1）
II、 二叉/項堆： O（V*lgV + |E|*lgV）
源點可達：O（E*lgV）
稀疏圖時，有E=o（V^2/lgV），
=> O（V^2）
III、斐波那契堆：O（V*lgV + E）
是的，由上，我們已經看出來了，Dijkstra 算法最快的實現是，采用斐波那契堆作最小優先隊列，算法時間復雜度，可達到O（V*lgV + E）。
但是列?如果題目有時間上的限制列?vlgv+e的時間復雜度，能否一定滿足要求?我們試圖尋找一種解決此最短路徑問題更快的算法。
這個時候，我們想到了Bellman-Ford算法：求單源最短路，可以判斷有無負權回路（若有，則不存在最短路），時效性較好，時間復雜度O（VE）。不僅時效性好於上述的Dijkstra 算法，還能判斷回路中是否有無負權回路。
既然，想到了Bellman-Ford算法，那麼時間上，是否還能做進一步的突破。對了，我們中國人自己的算法--SPFA算法：SPFA算法，Bellman-Ford的隊列優化，時效性相對好，時間復雜度O（kE）。（k<<V）。
是的，線性的時間復雜度，我想，再苛刻的題目，或多或少，也能滿足要求了。
什麼是SPFA算法
在上一篇文章二之三續、Dijkstra 算法+Heap堆的完整c實現源碼中，我們給出了Dijkstra+Heap堆的實現。其實，在稀疏圖中對單源問題來說SPFA的效率略高於 Heap+Dijkstra ；對於無向圖上的APSP(All Pairs Shortest Paths)問題，SPFA算法加上優化後效率更是遠高於Heap+Dijkstra。
那麼，究竟什麼是SPFA算法列?
SPFA算法，Shortest Path Faster Algorithm，是由西南交通大學段凡丁於1994年發表的。正如上述所說，Dijkstra 算法無法用於負權回路，很多時候，如果給定的圖存在負權邊，這時類似Dijkstra等算法便沒有了用武之地，而Bellman-Ford算法的復雜度又過高，SPFA算法便派上用場了。
簡潔起見，我們約定有向加權圖G不存在負權回路，即最短路徑一定存在。當然，我們可以在執行該算法前做一次拓撲排序，以判斷是否存在負權回路。
我們用數組d記錄每個結點的最短路徑估計值，而且用鄰接表來存儲圖G。
我們采取的方法是動態逼近法：設立一個先進先出的隊列用來保存待優化的結點，優化時每次取出隊首結點u，並且用u點當前的最短路徑估計值對離開u點所指向的結點v進行松弛操作，如果v點的最短路徑估計值有所調整，且v點不在當前的隊列中，就將v點放入隊尾。
這樣不斷從隊列中取出結點來進行松弛操作，直至隊列空為止。
定理: 只要最短路徑存在，上述SPFA算法必定能求出最小值。
期望的時間復雜度O(ke)， 其中k為所有頂點進隊的平均次數，可以證明k一般小於等於2。
SPFA實際上是Bellman-Ford基礎上的優化，以下，是此算法的偽代碼：
//這裡的q數組表示的是節點是否在隊列中，如q[v]=1則點v在隊列中
SPFA(G,w,s)
1. INITIALIZE-SINGLE-SOURCE(G,s)
2. Q ← Ø
3. for each vertex ∈ V[G]
4. q[v]=0
5. ENQUEUE(Q,s)
6. q[s]=1
7. while Q≠Ø
8. do u ← DEQUEUE(Q)
9. q[u]=0
10.for each edge(u,v) ∈ E[G]
11. do t ← d[v]
12. RELAX(u,v,w)
13. π[v] ← u
14. if (d[v] < t)
15. ENQUEUE(Q,v)
16. q[v]=1
SPFA是Bellman-Ford的隊列優化，時效性相對好，時間復雜度O（kE）。（k<<V）。
與Bellman-ford算法類似，SPFA算法采用一系列的松弛操作以得到從某一個節點出發到達圖中其它所有節點的最短路徑。所不同的是，SPFA算法通過維護一個隊列，使得一個節點的當前最短路徑被更新之後沒有必要立刻去更新其他的節點，從而大大減少了重復的操作次數。
與Dijkstra算法與Bellman-ford算法不同，SPFA的算法時間效率是不穩定的，即它對於不同的圖所需要的時間有很大的差別。在最好情形下，每一個節點都只入隊一次，則算法實際上變為廣度優先遍歷，其時間復雜度僅為O(E)。另一方面，存在這樣的例子，使得每一個節點都被入隊(V-1)次，此時算法退化為Bellman-ford算法，其時間復雜度為O(VE)。有研究指出在隨機情形下平均一個節點入隊的次數不超過2次，因此算法平均的時間復雜度為O(E)，甚至優於使用堆優化過的Dijkstra算法。
最短路徑問題的解決
浙大研究生復試2010年上機試題-最短路徑問題
問題描述：
給你n個點，m條無向邊，每條邊都有長度d和花費p，給你起點s終點t，要求輸出起點到終點的最短距離及其花費，如果最短距離有多條路線，則輸出花費最少的。
輸入：輸入n,m，點的編號是1~n,然後是m行，每行4個數 a,b,d,p，表示a和b之間有一條邊，且其長度為d，花費為p。最後一行是兩個數 s,t;起點s，終點t。n和m為0時輸入結束。
(1<n<=1000, 0<m<100000, s != t)
輸出：一行有兩個數， 最短距離及其花費。
接下來，咱們便利用SPFA 算法來解決此最短路徑問題。
以下，便引用sunbaigui的代碼來說明此問題：
聲明幾個變量：
int d[1005][2];
bool used[1005];
vector<Node>map[1005];
int N,M,S,T; 建個數據結構：
struct Node
{
int x,y,z;
Node(int a=0,int b=0
