Floyd算法
我們知道通過BFS或者DFS可以求出兩點之間的最短路徑荠锭，所以進行n^2次搜索，即對每兩個點都進行一次搜索，便可以求得任意兩點之間的最短路徑。
但懶人畢竟是懶人授段，有更快捷的代碼何樂而不為呢？
如果要讓任意兩點之間的路程變短番甩，只能引入第三個點（頂點k）侵贵，并通過這個頂點k中轉(zhuǎn)即i->k->j，才可能縮短原來從i點到j(luò)的路程缘薛。那么這個中轉(zhuǎn)的頂點k是1~n中的哪個點呢窍育？甚至有時候不只通過一個點，而是經(jīng)過兩個點或者更多點中轉(zhuǎn)會更短宴胧，即i->k1->k2->j或者i->k1->k2…->kn->j漱抓。
那么我們就有了DP方程：
dist[i][j]=min(dist[i][k]+dist[k][j])
通過這種方法我們可以只用O(V3)求出任意兩個點之間最短路徑。
正是因為它實現(xiàn)起來非常容易恕齐，如果時間復(fù)雜度要求不高乞娄，使用Floyd-Warshall來求指定兩點之間的最短路或者指定一個點到其余各個頂點的最短路徑也是可行的,適用于點數(shù)很少的圖。
//核心代碼
for(k=1;k<=n;k++)
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
if(e[i][j]>e[i][k]+e[k][j])
e[i][j]=e[i][k]+e[k][j];
/*Floyd-Warshall算法不能解決帶有“負權(quán)回路”（或者叫“負權(quán)環(huán)”）的圖，
因為帶有“負權(quán)回路”的圖沒有最短路补胚。
例如下面這個圖就不存在1號頂點到3號頂點的最短路徑码耐。
因為1->2->3->1->2->3->…->1->2->3這樣路徑中，
每繞一次1->-2>3這樣的環(huán)溶其，最短路就會減少1骚腥，永遠找不到最短路。
其實如果一個圖中帶有“負權(quán)回路”那么這個圖則沒有最短路瓶逃。*/
無權(quán)圖的最短路
BFS
源點設(shè)置成0束铭，和源點相連的設(shè)置成1，
以此類推厢绝，直到搜索結(jié)束所有點為止契沫；
BFS能很好地解決單源最短路徑的問題，
無權(quán)圖中昔汉，將權(quán)值視為單位長度即可懈万；
因為BFS本身是分層的，所以準確性是很有保障的
時間復(fù)雜度O(V+E)靶病，很常用的的算法
//核心代碼
這么簡單的算法会通，你還讓我貼代碼？
Dijkstra算法
時間復(fù)雜度O(V^2)娄周，類似Prim的想法涕侈，這么樸素的算法其實不怎么常用；
下面有能替代Dijkstra的國產(chǎn)算法SPFA煤辨；
請舉起火把裳涛，緊張地往下看！
SPFA
隊列優(yōu)化的Bellman—Ford算法
1.把源點的最短值當(dāng)做0众辨，入列
2.遍歷隊首頂點的初值端三，嘗試更新
3.如果某頂點的最短路徑值可能會改變，將其入列
4.重復(fù)操作
時間復(fù)雜度O(kE)泻轰，上限O(VE)
k一般是一個2左右的常數(shù)技肩，但是經(jīng)常有BT的出題人喜歡借此卡你
判斷負環(huán)
神奇的國產(chǎn)算法，記錄每個點入列的次數(shù)浮声，
當(dāng)其超過總點數(shù)V的時候虚婿，就證明存在負環(huán)
注意：雖然SPFA是替代Dijkstra的，但是泳挥，請千萬不要用Dijkstra判斷負環(huán)然痊！
堆優(yōu)化
SPFA中直接將隊列替換成單調(diào)隊列，每一次取出一個最短路徑估計值最小的頂點
當(dāng)圖中有負權(quán)邊的時候屉符，會瞬間變成指數(shù)級的時間復(fù)雜度··所以不要亂給SPFA優(yōu)化
