本周我们继续学习图分解算法，但现在是有向图的分解算法。

在本模块中，您将学习在图中寻找最短路径的算法。这些算法应用广泛。当你在智能手机上启动谷歌地图或 Yandex.Navi 等导航应用程序时，它会使用这些算法为你找到从公司到家、从家到学校等最快的路线。当你搜索飞机票时，这些算法会用来找到换乘飞机次数最少的路线。意想不到的是，这些算法还可以用来确定货币兑换的最佳方式，有时还能赚取巨额利润！我们将介绍所有这些应用，您将学习广度优先搜索、Dijkstra 算法和 Bellman-Ford 算法。这些算法非常高效，并为更高效的算法奠定了基础。您将在 "最短路径 "毕业设计项目中学习和实施这些算法，从而在城市和国家的真实地图上找到最佳路线，在社交网络中找到人与人之间的距离。最终你将能在任何图中高效地找到最短路径。本周我们将学习广度优先搜索算法。

本周我们继续学习图中的最短路径。你们将学习 Dijkstra 算法，该算法可用于寻找下班回家的最短路线。你还将学习贝尔曼-福德算法，它可以意外地用于选择货币兑换的最佳方式。最后，你将能在任何图中高效地找到最短路径。

在本模块中，我们将研究最小生成树问题。我们将介绍该问题的两种优雅的贪婪算法：第一种算法出自 Kruskal 之手，使用的是不相交集合数据结构；第二种算法出自 Prim 之手，使用的是优先队列数据结构。在本模块的编程作业中，您将计算城市间道路建设的最优方法，以及将给定对象集划分为簇的最优方法（数据挖掘中的一个基本问题）。

在本模块中，您将学习先进的最短路径算法，在现实世界的道路网络和社交网络图上，这些算法的实际运行速度比经典的 Dijkstra 算法快 1000 倍（最多 25000 倍）。您将基于这些算法开展一个编程项目。您将在美国部分地区的真实地图上找到最短路径，并在社交网络中找到连接人们的最短路径。我们鼓励你们不仅在实现过程中使用本模块讲座中的想法，而且提出自己的想法来加快算法的速度！我们鼓励你们在论坛上一较高下，看看谁的实现速度最快:)