最短路（基礎(chǔ)未優(yōu)化）
寫(xiě)在前面
寫(xiě)最短路我猶豫了很久，因?yàn)樽疃搪匪w的內(nèi)容很多（四個(gè)基礎(chǔ)算法）喘蟆，而且在基礎(chǔ)算法上還有許多不同的優(yōu)化缓升，甚至存邊都有幾種方式，就顯得特別復(fù)雜
基本概念
最短路就是求在一個(gè)圖中一個(gè)點(diǎn)到指定點(diǎn)的最短路程（其實(shí)光看名字就猜的出來(lái)）蕴轨。
幾個(gè)概念：
1.出發(fā)的點(diǎn)叫源點(diǎn)
2.一個(gè)點(diǎn)到另一個(gè)點(diǎn)的路程（也可以理解為連接這兩個(gè)點(diǎn)的線(xiàn)段的長(zhǎng)度）叫權(quán)
3.圖分兩種：有向圖和無(wú)向圖港谊。有向圖就像單行道，只能去不能回橙弱。而無(wú)向圖就像雙行道歧寺，可以去也可以回。
還有一些例如松弛操作這些的概念會(huì)在下面進(jìn)行解釋
基礎(chǔ)算法
存邊
對(duì)于一個(gè)圖棘脐，我們需要把邊存儲(chǔ)下來(lái)斜筐。而存儲(chǔ)有兩種方式糜值。
鄰接矩陣
用一個(gè)二維數(shù)組來(lái)存儲(chǔ)偎快。假如用數(shù)組k來(lái)存儲(chǔ)邊，則
k[i][j]
表示有一條從i到j(luò)的邊焚刚，權(quán)值為
k[i][j]
鄰接表
思路是用3個(gè)數(shù)組屈梁，（這里假設(shè)為a,b,c)（可能有點(diǎn)難理解）
當(dāng)
a[m]=I
b[m]=j
c[m]=n（其中m為常數(shù)）
就是表示從i到j(luò)有一條邊嗤练，權(quán)值為n。
但是假如要排序的話(huà)在讶，開(kāi)三個(gè)數(shù)組很麻煩煞抬，所以我建議用結(jié)構(gòu)體。而結(jié)構(gòu)體的排序方法我在講最小生成樹(shù)之kruskarl的時(shí)候講過(guò)构哺，這里就不再贅述革答。
前向星
前向星比鄰接矩陣省空間。
鏈?zhǔn)角跋蛐?/h5>
這個(gè)是一種鏈?zhǔn)降拇孢叿椒ㄊ锴俊＜偃缫?xì)講的話(huà)残拐，可能又要講一篇文章了，下文也不會(huì)使用這個(gè)旗扑。
感興趣的話(huà)可以去看這篇博客
https://blog.csdn.net/acdreamers/article/details/16902023/
無(wú)向邊
以上講的都是存有向邊的方式蹦骑。存無(wú)向邊其實(shí)區(qū)別不是很大慈省。舉個(gè)例子相信一下就懂了臀防。假如你要存一條從i到j(luò)的無(wú)向邊眠菇，你可以這么寫(xiě)
k[i][j]=n;
k[j][i]=n;
就是把終點(diǎn)和起點(diǎn)換一下位置，把終點(diǎn)當(dāng)起點(diǎn)袱衷，把起點(diǎn)當(dāng)終點(diǎn)捎废。
Floyd
這個(gè)算法有一大特點(diǎn)，那就是寫(xiě)起來(lái)極其簡(jiǎn)單（核心代碼只有5行）致燥，但是運(yùn)行效率極低（o（n^3））登疗，就讓它顯得很毒瘤，而且數(shù)據(jù)基本都會(huì)卡這種算法嫌蚤。
假如用二維數(shù)組
k[i][j]
來(lái)存儲(chǔ)從i到j(luò)的最段路辐益。
初始化：先把k數(shù)組全部賦一個(gè)很大很大的值（方便后面比較）
floyd算法如下
for(int k=1;k<=n;k++)//k枚舉途經(jīng)的節(jié)點(diǎn)
for(int i=1;i<=n;i++)//i枚舉起點(diǎn)
for(int j=1;j<=n;j++)//j枚舉終點(diǎn)
if(d[i][j]!=inf&&d[i][k]!=inf)//假如i到k沒(méi)有邊，那么假設(shè)不成立脱吱，同理智政，假如i到j(luò)沒(méi)有邊，這個(gè)假設(shè)也不成立
d[i][j]=min(d[i][k]+d[k][j],d[i][j]);//拿現(xiàn)有的從i到j(luò)的最段路和i途經(jīng)k再到j(luò)的總路程做比較箱蝠。（這就是為什么要把d[i][j]的初始值賦為一個(gè)很大的數(shù)）
可以看一下上面的注釋续捂。。
floyd就是靠三重循環(huán)來(lái)枚舉起點(diǎn)宦搬、途經(jīng)的點(diǎn)和終點(diǎn)牙瓢。然后做松弛操作。（松弛操作就是比大小那一步间校，有點(diǎn)像三角形的三邊關(guān)系）拿現(xiàn)有的從i到j(luò)的最段路和i途經(jīng)k再到j(luò)的總路程做比較矾克。也算是一個(gè)dp。
這個(gè)算法沒(méi)啥優(yōu)化（也沒(méi)啥可優(yōu)化的）撇簿∧粼ǎ可以求單源最段路（有向圖中的最段路），也可以求無(wú)向圖的最段路四瘫。不能對(duì)付負(fù)權(quán)
這里順便引入兩個(gè)新概念：負(fù)權(quán)&環(huán)
負(fù)權(quán)：一條權(quán)值為負(fù)的路（于現(xiàn)實(shí)生活中不存在）汉嗽。
環(huán)：有些時(shí)候在有向圖中會(huì)同時(shí)有從i到j(luò)和從j到i的兩條路。他們就組成了一個(gè)環(huán)找蜜。
負(fù)權(quán)環(huán)就是一個(gè)很恐怖的東西了饼暑，你可以靠負(fù)權(quán)環(huán)在環(huán)里面不停的刷，這樣你的最短路洗做。弓叛。。就成了無(wú)限的更短路诚纸。撰筷。。
dijkstra狄杰斯特拉算法
這是一個(gè)很經(jīng)典的單源最短路的算法畦徘。
這個(gè)算法的描述我覺(jué)得在一本叫算法圖解的書(shū)中描述的比較詳細(xì)毕籽，在這里就附上書(shū)的照片抬闯，覺(jué)得講得很通俗易懂，應(yīng)該理解沒(méi)有什么問(wèn)題关筒。（多圖預(yù)警）
總之就是重復(fù)那四步溶握，就可以找出最優(yōu)解。
算法效率比f(wàn)loyd不知道高到哪里去了蒸播。睡榆。
不能對(duì)付負(fù)權(quán)
bellman-ford貝爾曼福德算法
這是一個(gè)可以對(duì)付負(fù)權(quán)的算法
算法：
給你一個(gè)由v個(gè)點(diǎn)，e條邊的圖袍榆，和原點(diǎn)s
數(shù)組Distant[i]記錄從源點(diǎn)s到頂點(diǎn)i的路徑長(zhǎng)度胀屿，初始化
數(shù)組Distant[n]為, Distant[s]為0；
以下操作循環(huán)執(zhí)行至多n-1次包雀，n為頂點(diǎn)數(shù)：
對(duì)于每一條邊e(u, v)碉纳，如果Distant[u] + w(u, v) < Distant[v]，則另Distant[v] = Distant[u]+w(u, v)馏艾。w(u, v)為邊e(u,v)的權(quán)值劳曹；
若上述操作沒(méi)有對(duì)Distant進(jìn)行更新，說(shuō)明最短路徑已經(jīng)查找完畢琅摩，或者部分點(diǎn)不可達(dá)铁孵，跳出循環(huán)。否則執(zhí)行下次循環(huán)房资；
為了檢測(cè)圖中是否存在負(fù)環(huán)路蜕劝，即權(quán)值之和小于0的環(huán)路。對(duì)于每一條邊e(u, v)轰异，如果存在Distant[u] + w(u, v) < Distant[v]的邊岖沛，則圖中存在負(fù)環(huán)路，即是說(shuō)改圖無(wú)法求出單源最短路徑搭独。否則數(shù)組Distant[n]中記錄的就是源點(diǎn)s到各頂點(diǎn)的最短路徑長(zhǎng)度婴削。
可知，Bellman-Ford算法尋找單源最短路徑的時(shí)間復(fù)雜度為O(V*E).
Bellman－Ford算法可以大致分為三個(gè)部分
第一牙肝，初始化所有點(diǎn)唉俗。每一個(gè)點(diǎn)保存一個(gè)值，表示從原點(diǎn)到達(dá)這個(gè)點(diǎn)的距離配椭，將原點(diǎn)的值設(shè)為0虫溜，其它的點(diǎn)的值設(shè)為無(wú)窮大（表示不可達(dá)）。
第二股缸，進(jìn)行循環(huán)衡楞，循環(huán)下標(biāo)為從1到n－1（n等于圖中點(diǎn)的個(gè)數(shù)）。在循環(huán)內(nèi)部敦姻，遍歷所有的邊瘾境，進(jìn)行松弛計(jì)算坎背。
第三，遍歷途中所有的邊（edge（u寄雀，v）），判斷是否存在這樣情況：
d（v） > d (u) + w(u,v)
則返回false陨献，表示途中存在從源點(diǎn)可達(dá)的權(quán)為負(fù)的回路盒犹。
松弛操作之前講過(guò)，再看一遍復(fù)習(xí)一下
松弛計(jì)算之前眨业，點(diǎn)B的值是8急膀，但是點(diǎn)A的值加上邊上的權(quán)重2，得到5龄捡，比點(diǎn)B的值（8）小卓嫂，所以，點(diǎn)B的值減小為5聘殖。這個(gè)過(guò)程的意義是晨雳，找到了一條通向B點(diǎn)更短的路線(xiàn)，且該路線(xiàn)是先經(jīng)過(guò)點(diǎn)A奸腺，然后通過(guò)權(quán)重為2的邊餐禁，到達(dá)點(diǎn)B。
當(dāng)然突照，如果出現(xiàn)以下情況
則不會(huì)修改點(diǎn)B的值帮非，因?yàn)?＋4>6。
spfa留著下次再講（和優(yōu)化一起讹蘑，因?yàn)樗容^難末盔。。）座慰。（留坑待補(bǔ)）
會(huì)了Bellman－Ford算法和狄杰斯特拉算法就已經(jīng)可以做一些最段路的題了陨舱，可以練習(xí)一下。
重點(diǎn)理解：松弛操作（這玩意真的很重要版仔，基本上最段路的精髓就是它了）
tks隅忿！
（參考文獻(xiàn)：https://www.cnblogs.com/tanky_woo/archive/2011/01/17/1937728.html ， 算法圖解）
