最短路算法总结

对于最短路的学习，刚开始是做模板题，对于几种算法并不怎么理解，后来逐渐的做题查资料中渐渐的有了一点自己的理解，对于最短路算法，大致有以下几种：

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的队列优化形式。

以上就是我对最短路算法的理解。