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

讲解第6章的内容 186-198页

重点:

1、最小生成树算法

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

2、最短路径 算法

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

本周公布综合实验，涉及大作业的内容，请大家关注教学公告

师说

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