数据结构与算法（c 描述）-k8凯发旗舰

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

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

重点

1、最小生成树算法

prim普里姆算法、kruskal克鲁斯卡尔算法

2、最短路径算法

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

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

师说

图的最重要的应用之一就是在交通运输和通信网络中寻找最短路径，对路径进行规划。比如:乘坐汽车旅行的人总希望找到目的地尽可能短的行程。如果有一张地图并在每对十字路口标出距离，如何找出这一最短行程?

一种可能的方法就是枚举出所有的路径，并计算每条路径的长度，然后选择最短的一条。那么，我们很容易看到，即使不包含回路的路径，依然存在数以百万计的行车路线，而其中绝大数是不值得考虑的。

本周我们将阐明将如何有效的解决这类问题。图的最短路径算法在工程实践中有很多应用，如工程布线、神经网络、消防选址、茶叶运输等均有应用，具体可以登录学校图书馆查看相关论文研读。

推荐阅读