|
|
教学公告
讲授内容
讲解第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://blog.csdn.net/u012416259/article/details/98334588
- 克隆图
- 课程表II
- 网络延迟问题
- 除法求值
- 最小高度树
- 重新安排行程
- 冗余连接
