最短路算法總結

對于最短路的學習，剛開始是做模闆題，對于幾種算法并不怎麼了解，後來逐漸的做題查資料中漸漸的有了一點自己的了解，對于最短路算法，大緻有以下幾種：

Dijkstra, Floyd, Bellman-Ford，SPFA幾種，這幾種算法各有特點和用處，下面是我的一些了解。

• Dijkstra算法 ：

首先，這種算法的前提是權值圖中不存在負權邊，這個算法的主要思想是貪心思想，Dijkstra算法是單源最短路利用dis數組存儲從起點到其他點的最短路，剛開始存儲的是起始點到其他點的初始路程，通過n-1次周遊找到最短路， 該算法通過n-1次的松弛使起始點到其他點的路程變為最小，算法主題：if(mindis+Map[min][j]<dis[j] && Map[min][j]!=INF && vis[j]==0)

dis[j] = mindis+Map[min][j];

每次從dis數組中選出一個值最小的節點然後标記這個節點對這個點連接配接的每一條邊進行松弛。因為每次都是找最小值，是以不能存在負權邊，因為存在負權邊會使路徑無限變小。

二、Floyd算法  ：

這種算法可以找多源最短路，要想找到兩點間的最短路，隻能通過找中間點，來縮短路徑，Floyd的算法主題思想是動态規劃，核心代碼隻有五行，通過從1到n的周遊找出每一個中間點，查找所有中間值，最終使得兩點間得距離達到最小。

算法主體 ：

for(int k=1; k<=n; k++)

for(int i=1; i<=n; i++)

for(int j=1; j<=n; j++)

{

if(map1[i][j]>map1[i][k]+map1[k][j])

map1[i][j]=map1[i][k]+map1[k][j];

}

實際運用中可以通過改變map數組的含義來計算題目所需要的東西。

• bellman-ford與SPFA算法（帶負權的最短路問題） ：

這種算法可以計算負權值，一般用于有負權值的最短路，這個算法也是通過周遊n-1遍找過所有的點，因為最短路是一個不包含回路的路徑，正負回路都不能有，去掉回路以後，n個點就隻剩下了n-1條邊，但是這個循環有可能不到n-1次就找到了所有最短路，最壞的情況是n-1次循環。

算法主體：

for(int k=1;k<=n-1;k++)//進行n-1次松弛

for(int i=1;i<=m;i++)//枚舉每一條邊

if(dis[v[i]]>dis[u[i]]+w[i])//嘗試松弛每一條邊

dis[v[i]]=dis[u[i]]+w[i];

判斷負權回路時隻需要所有點松弛一遍後看能不能繼續松弛，如果還能松弛則代表存在負權回路，正權會路隻需改變一下就好。

• spfa（隊列優化的bellman） ：

Spfa是bellman的隊列優化形式。

以上就是我對最短路算法的了解。