最短路算法理解

￡神魔★判官ぃ 2022-05-18 02:26 219阅读 0赞

#                                       最短路算法理解 #

对于最短路的学习，主要学习了弗洛伊德Floyd算法、迪杰斯特拉Dijkstra算法、Bellman-Ford算法、自己又在网上看了一些spfa求最短路；对于Bellman-Ford的队列优化建立邻接表自己没有理解好。

弗洛伊德算法对于求最短路是最容易理解的，直接五行代码就能够实现，对于每个点都进行绕行判断一次看是否e\[i\]\[j\]>e\[i\]\[k\]+e\[k\]\[j\];如果成立说明经过绕行可以使两点之间的距离变短，经过了对每一个点的绕行判断将每一个能够松弛的边进行了松弛，弗洛伊德最后是求出的所有的各个点之间的最短路，当然它的复杂度也是特别高的；在此次的练习中有两道题一道是判断负权回路[https://blog.csdn.net/kongsanjin/article/details/81224406][https_blog.csdn.net_kongsanjin_article_details_81224406]，一道是判断正权回路[https://blog.csdn.net/kongsanjin/article/details/81257028][https_blog.csdn.net_kongsanjin_article_details_81257028]，在网上看到也有人用弗洛伊德写了，自己也写了一下；判断负权回路是在进行弗洛伊德算法时，判断松弛是否会出现一个点到它本身为负权若出现了负权，就说明形成了负权回路；当判断出为负权回路时要跳出循环，不然会超时。判断正权回路的是进行了两遍弗洛伊德，判断经过一遍弗洛伊德后再进行弗洛伊德看是否有权变大，若继续变大了话，说明构成了正权回路。

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];

迪杰斯特拉算法是求单源最短路的，将一个点到其他各个点的最短路存到了dis\[\]数组中，它是每次找出它未绕行过且到它最短的点，从这个点绕行若经过绕行其他的点的距离变小了就进行松弛；这样循环n-1次就松弛完了（当然也可能不用n-1次就松弛完了）对于此次的练习题有一些是对迪杰斯特拉算法的变形；有的求的是使路径中的最大值最小（使青蛙每次不用跳这么远的距离）[https://blog.csdn.net/kongsanjin/article/details/81220083][https_blog.csdn.net_kongsanjin_article_details_81220083]有的求的是使最小值最大（使道路的负重能力大，为了多拉货物）[https://blog.csdn.net/kongsanjin/article/details/81206278][https_blog.csdn.net_kongsanjin_article_details_81206278]；其实核心算法还是没变只是dis\[\]数组存储的不同了，判断条件不同了。

for(i=1;i<n;i++)
    {
        min=inf;
        for(j=1;j<=n;j++)
        {
            if(book[j]==0&&dis[j]<min)
    	{
    	    min=dis[j];
    	    u=j;
    	}
        }
        book[u]=1;
        for(v=1;v<=n;v++)
        {
    	if(map[u][v]<inf)
    	{
                if(dis[v]>dis[u]+map[u][v])
    		dis[v]=dis[u]+map[u][v];
    	}
    }

Bellman-Ford算法是求含有负权值的边的，与弗洛伊德和迪杰斯特拉不同的是它未将边都存入地图中，而是直接对边进行松弛，若dis\[b\[i\]\]>dis\[a\[i\]\]+c\[i\];如果现在到终点b\[i\]的路径大于经过起点a\[i\]点和两点间的路径和时，就进行松弛；Bellman-Ford算法也能够判断负权环，如果经过了n-1轮的松弛过后还能进行松弛说明存在负权环。那道求正权环的题就是对求负权环的变形，dis\[\]数组初始值改变，判断条件改变就行了。

for(k=1;k<n;k++)
    {
    	f=0;//用来标记本轮松弛dis数组是否发生更新 
    	for(i=1;i<=m;i++)
    	{
    		if(dis[b[i]]>dis[a[i]]+c[i])
    		{
    			dis[b[i]]=dis[a[i]]+c[i];
    			f=1;
    		}
    	}
    	if(f==0)//没有更新跳出 
    		break;
    }
    flag=0;
    for(i=1;i<=m;i++)
    {
    	if(dis[b[i]]>dis[a[i]]+c[i])
    		flag=1;
    }
    if(flag==1)
    	printf("有负权回路\n");
    else
    	printf("没有负权回路\n");

从网上看的题解用Spfa的dfs算法写了一道求从矩阵的左上角到右下角的最短时间的题；自己先用深搜dfs敲了一遍超时，看了spfa是和bfs差不多，多了一个对队首的标记取消和当到某一点的时间如果可以变短的话进行松弛，还是dis数组存储的到各个点的最小权，还有就是对那道题的无穷大inf不能为八个9，会答案错误，必须是无穷大2147483647[https://blog.csdn.net/kongsanjin/article/details/81261737][https_blog.csdn.net_kongsanjin_article_details_81261737]。

### 注意：解题时权值是单向还是双向 ###

[https_blog.csdn.net_kongsanjin_article_details_81224406]: https://blog.csdn.net/kongsanjin/article/details/81224406
[https_blog.csdn.net_kongsanjin_article_details_81257028]: https://blog.csdn.net/kongsanjin/article/details/81257028
[https_blog.csdn.net_kongsanjin_article_details_81220083]: https://blog.csdn.net/kongsanjin/article/details/81220083
[https_blog.csdn.net_kongsanjin_article_details_81206278]: https://blog.csdn.net/kongsanjin/article/details/81206278
[https_blog.csdn.net_kongsanjin_article_details_81261737]: https://blog.csdn.net/kongsanjin/article/details/81261737