您申请加入课程:数据结构与算法(C++描述)
需要验证您的身份,请输入请求信息:
您的学号:
班级选择:
附注信息:
  • 创建者

    Creator

    潘家辉
  • 活跃度

    Activeness

  • 访问量

    Visits

    113708

教学公告

19软工 第11周安排
[作者: 潘家辉  发布时间:2020-11-15 16:10:10  浏览次数:535次]

19软件工程《数据结构与算法》 第11周安排


讲解第6章的内容 188-200页

重点

1、最小生成树算法

Prim普里姆算法、Kruskal克鲁斯卡尔算法

2、最短路径算法

迪杰斯特拉算法、弗洛伊德算法

本周已提前公布综合实验,涉及大作业的内容,请大家关注学者网作业内容



师说

图的最重要的应用之一就是在交通运输和通信网络中寻找最短路径。例如在交通网络中经常会遇到这样的问题:两地之间是否有公路可通;在有多条公路可通的情况下,哪一条路径是最短的等等。这就是带权图中求最短路径的问题,此时路径的长度不再是路径上边的数目总和,而是路径上的边所带权值的和。带权图分为无向带权图和有向带权图,但如果从A地到B地有一条公路,A地和B地的海拔高度不同,由于上坡和下坡的车速不同,那么边和边上表示行驶时间的权值也不同。考虑到交通网络中的这种有向性,课本只讨论有向带权图的最短路径。一般习惯将路径的开始顶点成为源点,路径的最后一个顶点成为终点。

除了课本上的Dijkstra算法和Floyd算法,还有一种SPFA算法,求单源最短路的SPFA算法的全称是:Shortest Path Faster Algorithm。 最短路径快速算法-SPFA算法是西南交通大学段凡丁于1994年发表的,我读书的时候觉得这个非常牛,我国的研究人员在这些经典算法上也是有所建树的。有时候大家碰到的一些ACM题目里面,SPFA可能就是解题神器,例如负权边等,而且它可以很方便地把优先权结合到自身的队列里面,值得有兴趣的同学了解一些。

  适用范围:给定的图存在负权边,这时类似Dijkstra等算法便没有了用武之地,而Bellman-Ford算法的复杂度又过高,SPFA算法便派上用场了。 我们约定有向加权图G不存在负权回路,即最短路径一定存在。当然,我们可以在执行该算法前做一次拓扑排序,以判断是否存在负权回路,但这不是我们讨论的重点。

算法思想:我们用数组d记录每个结点的最短路径估计值,用邻接表来存储图G。我们采取的方法是动态逼近法:设立一个先进先出的队列用来保存待优化的结点,优化时每次取出队首结点u,并且用u点当前的最短路径估计值对离开u点所指向的结点v进行松弛操作,如果v点的最短路径估计值有所调整,且v点不在当前的队列中,就将v点放入队尾。这样不断从队列中取出结点来进行松弛操作,直至队列空为止。

算法来源:

https://xueshu.baidu.com/usercenter/paper/show?paperid=39798c8bf2d1b5236cdaae3152d490ed&site=xueshu_se


思考

同学们比较关心目前面试笔试中数据结构的内容,可以参考一下比较多人再CSDN使用的图。


本周讲述的最短路径也是热门知识点之一,例如2018年华为笔试题,是一道灵活应用的大题,值得一读。

大家可以思考一下,答案在最后的链接上。



https://blog.csdn.net/li775085737/article/details/80273365



相关课程

扫一扫二维码,快速加入本课程!

放大二维码 查看使用方法
关闭