最短路優(yōu)化
寫在前面
上次講了最短路的基礎(chǔ)，但是像最短路這種博大精深（坑特別深）的算法。。。是肯定有優(yōu)化的啦。這一篇是給有最短路基礎(chǔ)的人看的，假如沒有嘛。。可以看看我以前寫的最短路基礎(chǔ)
SPFA
我把這個算法挪到這邊來寫了，原因有兩個：第一個是我上次懶得寫了。。
第二個是這個算法比較難，所以放在了優(yōu)化這邊一起寫，而且它本身就是對貝爾曼福德的優(yōu)化。
不說廢話了，let's begin
spfa 算法可以適用于負(fù)邊權(quán)的情況，是 bellman-ford 的隊列優(yōu)化。
假設(shè)存在 G=<V,E>，dis[i]記錄 V0 到 i 的最短距離，pre[i]記錄從 V0 到 i 路徑 上 i 的前面的一個頂點;
step1.將所有頂點對之間距離初始化為無窮大(dis[i][j]=無窮大)，pre[i]=i， vis[i]=0，將源點入隊;
step2.讀取隊頭頂點 now，并將隊頭頂點 now 出隊(記得消除標(biāo)記)，將與點 now 相連的所有點 next 進(jìn)行松弛操作（還記得嗎，上一篇講過），更新 dis[next]，另外，如果點 next 沒有 在隊列中，那么要將點 next 入隊(記得標(biāo)記)，如果已經(jīng)在隊列中了，那么就不 用入隊(如果某個頂點入隊超過 V 次，則說明圖中有負(fù)環(huán)，直接跳出);
step3.重復(fù) step2，直到隊空為止就完成了單源最短路的求解。
這是主要思路。
下面有個圖解（無恥的轉(zhuǎn)自某博客）??
其實它和bfs非常類似（bfs在我創(chuàng)建的專題里有人講過）。只是bfs中的一個點出了隊列就不會再回來了，而最段路中由于有環(huán)的存在，導(dǎo)致了一個點可能進(jìn)入隊列多次。
spfa函數(shù)附上
下面是洛谷題解的一個，感覺注釋寫的挺詳細(xì)，也附上。
void spfa()
{
queue<int> q; //spfa用隊列，這里用了STL的標(biāo)準(zhǔn)隊列
for(int i=1; i<=n; i++)
{
dis[i]=inf; //帶權(quán)圖初始化
vis[i]=0; //記錄點i是否在隊列中，同dijkstra算法中的visited數(shù)組
}
q.push(s); dis[s]=0; vis[s]=1; //第一個頂點入隊，進(jìn)行標(biāo)記
while(!q.empty())
{
int u=q.front(); //取出隊首
q.pop(); vis[u]=0; //出隊標(biāo)記
for(int i=head[u]; i; i=edge[i].next) //鄰接表遍歷，不多解釋了（也可用vector代替）
{
int v=edge[i].to;
if(dis[v]>dis[u]+edge[i].dis) //如果有最短路就更改
{
dis[v]=dis[u]+edge[i].dis;
if(vis[v]==0) //未入隊則入隊
{
vis[v]=1; //標(biāo)記入隊
q.push(v);
}
}
}
}
}
spfa這個算法非常好用（功能強(qiáng)大，效率高??）
基本上單源最短路的題都可以用spfa，墻裂推薦
狄杰斯特拉（堆優(yōu)化）
真不知道為什么會有人把它念成迪克特斯拉??
（需要有堆的基礎(chǔ)）
思路：在尋找周圍最小點的時候，用最小堆，可以用 O(log n)的時間找出最小的可到達(dá)點。
是不是感覺很蛋疼。。但是很秀??
最小堆：最小堆，是一種經(jīng)過排序的完全二叉樹，其中任一非終端節(jié)點的數(shù)據(jù)值均不大于其左子節(jié)點和右子節(jié)點的值。
最小堆后面可能會說，但是這里嘛。。就很不負(fù)責(zé)任的推薦一個別人的博客：別人家的最小堆
別嫌棄呀。。
堆優(yōu)化的主要思想就是使用一個優(yōu)先隊列（就是每次彈出的元素一定是整個隊列中最小的元素）來代替最近距離的查找，用鄰接表代替鄰接矩陣，這樣可以大幅度節(jié)約時間。
在這里有幾個坑要先填一下：
首先來講，優(yōu)先隊列的數(shù)據(jù)類型應(yīng)該是怎樣的呢？
我們知道優(yōu)先隊列應(yīng)該用于快速尋找距離最近的點。由于優(yōu)先隊列只是將最小的那個元素排在前面，因此我們應(yīng)該定義一種數(shù)據(jù)類型，使得它包含該節(jié)點的編號以及該節(jié)點當(dāng)前與起點的距離。
辣么。。我們應(yīng)該在什么時候?qū)﹃犃羞M(jìn)行操作呢？
隊列操作的地方，首先就是搜索剛開始，要為起點賦初始值，此時必須將起點加入優(yōu)先隊列中。該隊列元素的節(jié)點編號為起點的編號，該節(jié)點當(dāng)前與起點的距離為0。
那么如果一個節(jié)點到起點的最短距離通過其他的運(yùn)算流程發(fā)生了變化，那么如何處理隊列中的那個已經(jīng)存入的元素？
事實上，你不需要理會隊列中的元素（暴力無視），而是再存入一個就行了。因為如果要發(fā)生變化，只能將節(jié)點與起點之間的距離變得更小，而優(yōu)先隊列恰好是先讓最小的那個彈出。
因此，輪到某一個隊列元素彈出的時候，如果有多個元素的節(jié)點編號相同，那么被彈出的一定是節(jié)點編號最小的一個。等到后面再遇到這個節(jié)點編號的時候，我們只需要將它忽略掉就行了。
是不是感覺hin棒？??
最小堆優(yōu)化的迪杰有一個模版題：
例:網(wǎng)吧
【問題背景】
綿陽中學(xué)以人數(shù)眾多而聞名。三個年級共有 10000 多人，學(xué)生多了附近的 網(wǎng)吧也多。Mzoiers 都熱衷于 Dota，可學(xué)校的機(jī)子配置相當(dāng)差(評測服務(wù)器除外)， 根本不能玩 Dota，那就只有去網(wǎng)吧。星期天到星期五都是晚上 10:20 才下晚自 習(xí)，幾乎沒時間玩。
然而星期六下午放假是絕好的時間，但是學(xué)校人多啊，一放學(xué)去網(wǎng)吧的人就 開始狂奔，競爭之激烈，搶到機(jī)子的難度非常之大。往往在我們到達(dá)網(wǎng)吧之前都 坐滿了。
學(xué)校到網(wǎng)吧的路是錯綜復(fù)雜的，以致于到一個自己想去的網(wǎng)吧都有非常多的 路線可以選擇，而路線的長度又不相同，這樣就決定了要花費的時間，因此想要 盡快到達(dá)，選擇一條最佳的線路是很有必要的。
【問題描述】
為了簡化問題，我們把學(xué)校與周邊的網(wǎng)吧看做圖中的頂點，學(xué)校與網(wǎng)吧，網(wǎng) 吧與網(wǎng)吧之間的路線看做邊，每個邊都有一個權(quán)，表示我們走完這條路的時間， 由于放學(xué)人流量大，如果反向走會有危險，因此這是一個有向圖。
我的的學(xué)校在 S 點，想要去的網(wǎng)吧在 T 點。你的任務(wù)就是選擇一條最佳路線， 使得從學(xué)校到目的地網(wǎng)吧的時間最短，你只需要輸出最短到達(dá)時間即可。 【輸入文件】
netbar.in 中共有 M+2 行數(shù)據(jù)
第一行兩個整數(shù) N，M，表示點數(shù)和邊數(shù)。
然后 M 行每行 3 個正整數(shù)(u，v，t)，表示有一條可由 u 到 v 耗時為 t 的邊。 最后一行兩個正整數(shù) S、T。
【輸出文件】
netbar.out 中，只有一行，一個整數(shù)表示最短時間。如果 S、T 之間不存在通 路則輸出“No Solution!”(雙引號不輸出，“!”為西文標(biāo)點)。
【輸入樣例】
44 123 2 4 10 135 345 14
【輸出樣例】
10
【數(shù)據(jù)規(guī)模】
對于 30%的數(shù)據(jù)保證有 1<N<=1000，1<=M<=1000; 對于全部的數(shù)據(jù)保證有 1<N<=10000，1<=M<=100000。
注明：我不是綿中的（也不打算去），我和綿中也沒有什么利益關(guān)系。題目不是我出的，如果覺得它對綿中不懷好意。。。也別找我
下面附上標(biāo)程：
迪杰優(yōu)化一般情況下用的不是很多，但是在某些特殊場合是可以用的。也看得出來優(yōu)化不是很復(fù)雜，比較好理解。對迪杰情有獨鐘的同學(xué)可以記一下。
ending
最短路這個博大精深的算法也算是圖論的核心，所以。。學(xué)好最短路很重要。
看在我這么用心的份上滋瓷一下唄。。
不要問我為什么這篇的程序都是圖片。。
其實。。介紹一個方法（也不知道算不算了）。在遇到最段路的題的時候，windows系統(tǒng)的同學(xué)可以打開畫圖，把樣例畫成一個圖，在推一遍，可以看得很直觀，免得對著幾個數(shù)字空想，很抽象。
（老師附體）（苦口婆心）以上內(nèi)容可能有點難度，建議多看幾遍，多想幾下，最好能推一遍。。。
（在你嫌棄我之前跑掉）??
