不知不觉7天了，甚至开始有点想偷懒了...
第13章 最短路径
寻找最短路径是一个重要的问题，有着很多的应用。在一个无权图当中，最短路径的寻找可以直接使用广度优先算法。所以这一章主要讨论带权图。
第一节，Bellman-Ford algorithm，我翻译不来呢^.^在有负权环图的算法中不适用，但是可以侦测负权环，用于寻找一个点到其他点的最短路径。感觉是个暴力算法，大概就是执行N-1轮算法，因为最短路径最长有N-1个边，每一轮都遍历所有的边，看看距离能不能缩短。如果要侦测负权环的话就执行N轮，如果第N轮路径长度还在下降，就可以断定有负权环。最后介绍了一个这个算法的变种SPFA，具体看书...
第二节，Dijkstra's algorithm（迪杰斯特拉算法），只能处理不带有负权边的图，也是用来寻找一个点到其他点的最短路径。其实从这个算法的性质也可以看出，每一个点最多被访问一次，每一次访问都会确定起始点到该点的最短路径，所以在遇到负权边的时候都没有反应...算法当中使用了优先级队列来寻找还没有遍历过的距离最短的点。
第三节，Floyd-Warshall algorithm（弗洛伊德算法），寻找点之间的最短路径，暴力美学。
第14章 树算法（Tree algorithms）
作者先介绍了一下树的一些基本概念，看书...
第一节，树的遍历，作者举了个深度优先遍历的例子。然后提了一下在遍历的时候使用动态规划来记录一些信息。
第二节，直径（Diameter），介绍了两种算法来计算树的直径。第一种是随便找一个根节点后寻找离根节点最远的分别在两个不同子树的两个叶子。第二种是随便选一点，先找离这个点最远的节点，然后用找到的点再找离这个点最远的节点。
第三节，所有最长路径，找每一个节点的最长路径。先随便找个根节点，先计算每一节点两个经过不同子节点的最长路径，然后计算经过父节点的最长路径。然后Over。主要第一部分计算的经过两个不同子节点的最长路径需要揣摩一下。
第四节，二叉树（Binary trees），主要介绍了一下前序后序中序遍历。
预告
明天的两章分别是生成树（Spanning trees）和有向图（Directed graphs），图之一道，博大精深啊!