最短路優(yōu)化
寫在前面
上次講了最短路的基礎(chǔ)弦追，但是像最短路這種博大精深（坑特別深）的算法。花竞。劲件。是肯定有優(yōu)化的啦。這一篇是給有最短路基礎(chǔ)的人看的约急，假如沒有嘛零远。⊙岜危可以看看我以前寫的最短路基礎(chǔ)
SPFA
我把這個算法挪到這邊來寫了牵辣，原因有兩個：第一個是我上次懶得寫了。奴饮。
第二個是這個算法比較難纬向，所以放在了優(yōu)化這邊一起寫，而且它本身就是對貝爾曼福德的優(yōu)化戴卜。
不說廢話了罢猪，let's begin
spfa 算法可以適用于負邊權(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 出隊(記得消除標記)汤徽，將與點 now 相連的所有點 next 進行松弛操作（還記得嗎娩缰，上一篇講過），更新 dis[next]谒府，另外拼坎，如果點 next 沒有 在隊列中，那么要將點 next 入隊(記得標記)完疫，如果已經(jīng)在隊列中了泰鸡，那么就不 用入隊(如果某個頂點入隊超過 V 次，則說明圖中有負環(huán)壳鹤，直接跳出);
step3.重復(fù) step2盛龄，直到隊空為止就完成了單源最短路的求解。
這是主要思路芳誓。
下面有個圖解（無恥的轉(zhuǎn)自某博客）??
其實它和bfs非常類似（bfs在我創(chuàng)建的專題里有人講過）余舶。只是bfs中的一個點出了隊列就不會再回來了，而最段路中由于有環(huán)的存在锹淌，導(dǎo)致了一個點可能進入隊列多次匿值。
spfa函數(shù)附上
下面是洛谷題解的一個，感覺注釋寫的挺詳細赂摆，也附上挟憔。
void spfa()
{
queue<int> q; //spfa用隊列，這里用了STL的標準隊列
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; //第一個頂點入隊曲楚，進行標記
while(!q.empty())
{
int u=q.front(); //取出隊首
q.pop(); vis[u]=0; //出隊標記
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; //標記入隊
q.push(v);
}
}
}
}
}
spfa這個算法非常好用（功能強大褥符，效率高??）
基本上單源最短路的題都可以用spfa，墻裂推薦
狄杰斯特拉（堆優(yōu)化）
真不知道為什么會有人把它念成迪克特斯拉??
（需要有堆的基礎(chǔ)）
思路：在尋找周圍最小點的時候抚垃，用最小堆喷楣，可以用 O(log n)的時間找出最小的可到達點。
是不是感覺很蛋疼鹤树。铣焊。但是很秀??
最小堆：最小堆，是一種經(jīng)過排序的完全二叉樹罕伯，其中任一非終端節(jié)點的數(shù)據(jù)值均不大于其左子節(jié)點和右子節(jié)點的值曲伊。
最小堆后面可能會說，但是這里嘛。坟募。就很不負責任的推薦一個別人的博客：別人家的最小堆
別嫌棄呀岛蚤。。
堆優(yōu)化的主要思想就是使用一個優(yōu)先隊列（就是每次彈出的元素一定是整個隊列中最小的元素）來代替最近距離的查找懈糯，用鄰接表代替鄰接矩陣涤妒，這樣可以大幅度節(jié)約時間。
在這里有幾個坑要先填一下：
首先來講赚哗，優(yōu)先隊列的數(shù)據(jù)類型應(yīng)該是怎樣的呢她紫？
我們知道優(yōu)先隊列應(yīng)該用于快速尋找距離最近的點。由于優(yōu)先隊列只是將最小的那個元素排在前面屿储，因此我們應(yīng)該定義一種數(shù)據(jù)類型贿讹，使得它包含該節(jié)點的編號以及該節(jié)點當前與起點的距離。
辣么扩所。围详。我們應(yīng)該在什么時候?qū)﹃犃羞M行操作呢？
隊列操作的地方祖屏，首先就是搜索剛開始助赞，要為起點賦初始值，此時必須將起點加入優(yōu)先隊列中袁勺。該隊列元素的節(jié)點編號為起點的編號雹食，該節(jié)點當前與起點的距離為0。
那么如果一個節(jié)點到起點的最短距離通過其他的運算流程發(fā)生了變化期丰，那么如何處理隊列中的那個已經(jīng)存入的元素群叶？
事實上，你不需要理會隊列中的元素（暴力無視）钝荡，而是再存入一個就行了街立。因為如果要發(fā)生變化，只能將節(jié)點與起點之間的距離變得更小埠通，而優(yōu)先隊列恰好是先讓最小的那個彈出赎离。
因此，輪到某一個隊列元素彈出的時候端辱，如果有多個元素的節(jié)點編號相同梁剔，那么被彈出的一定是節(jié)點編號最小的一個。等到后面再遇到這個節(jié)點編號的時候舞蔽，我們只需要將它忽略掉就行了荣病。
是不是感覺hin棒？??
最小堆優(yōu)化的迪杰有一個模版題：
例:網(wǎng)吧
【問題背景】
綿陽中學(xué)以人數(shù)眾多而聞名渗柿。三個年級共有 10000 多人个盆，學(xué)生多了附近的 網(wǎng)吧也多。Mzoiers 都熱衷于 Dota，可學(xué)校的機子配置相當差(評測服務(wù)器除外)颊亮， 根本不能玩 Dota鸡岗，那就只有去網(wǎng)吧。星期天到星期五都是晚上 10:20 才下晚自 習编兄，幾乎沒時間玩轩性。
然而星期六下午放假是絕好的時間，但是學(xué)校人多啊狠鸳，一放學(xué)去網(wǎng)吧的人就 開始狂奔揣苏，競爭之激烈，搶到機子的難度非常之大件舵。往往在我們到達網(wǎng)吧之前都 坐滿了卸察。
學(xué)校到網(wǎng)吧的路是錯綜復(fù)雜的，以致于到一個自己想去的網(wǎng)吧都有非常多的 路線可以選擇铅祸，而路線的長度又不相同坑质，這樣就決定了要花費的時間，因此想要 盡快到達临梗，選擇一條最佳的線路是很有必要的涡扼。
【問題描述】
為了簡化問題，我們把學(xué)校與周邊的網(wǎng)吧看做圖中的頂點盟庞，學(xué)校與網(wǎng)吧吃沪，網(wǎng) 吧與網(wǎng)吧之間的路線看做邊，每個邊都有一個權(quán)什猖，表示我們走完這條路的時間票彪， 由于放學(xué)人流量大，如果反向走會有危險不狮，因此這是一個有向圖降铸。
我的的學(xué)校在 S 點，想要去的網(wǎng)吧在 T 點摇零。你的任務(wù)就是選擇一條最佳路線推掸， 使得從學(xué)校到目的地網(wǎng)吧的時間最短，你只需要輸出最短到達時間即可遂黍。 【輸入文件】
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!”(雙引號不輸出带到，“!”為西文標點)。
【輸入樣例】
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)系。題目不是我出的闪金，如果覺得它對綿中不懷好意疯溺。。哎垦。也別找我
下面附上標程：
迪杰優(yōu)化一般情況下用的不是很多囱嫩，但是在某些特殊場合是可以用的。也看得出來優(yōu)化不是很復(fù)雜漏设，比較好理解挠说。對迪杰情有獨鐘的同學(xué)可以記一下。
ending
最短路這個博大精深的算法也算是圖論的核心愿题，所以损俭。。學(xué)好最短路很重要潘酗。
看在我這么用心的份上滋瓷一下唄杆兵。。
不要問我為什么這篇的程序都是圖片仔夺。琐脏。
其實。缸兔。介紹一個方法（也不知道算不算了）日裙。在遇到最段路的題的時候，windows系統(tǒng)的同學(xué)可以打開畫圖惰蜜，把樣例畫成一個圖昂拂，在推一遍，可以看得很直觀抛猖，免得對著幾個數(shù)字空想格侯，很抽象鼻听。
（老師附體）（苦口婆心）以上內(nèi)容可能有點難度，建議多看幾遍联四，多想幾下撑碴，最好能推一遍。朝墩。醉拓。
（在你嫌棄我之前跑掉）??
