第七章第二节 最短路径
无权最短路径
对图中一个顶点，找出它到图中所有其他顶点的最短路径。对于找出图G=(E,V)中顶点s到其他顶点的最短路径：
初始：两个集合——Cur与Next，Cur为{s}，Next为s相邻的顶点的集合；s到Next中顶点v的最短路径为L(s,v)=(s,v)；
循环：将Cur更新为Next，将Next更新为Cur中顶点相邻的顶点；s到Next中顶点v的最短路径为L(s,v)=(L(s,u),v)，其中u为使得v进入Next中的顶点；
Dijkstra算法
如果是有权图，则需要使用Dijkstra算法求最短路径。
初始：集合K包含已知最短路径的节点；K初始为空；D为s到所有顶点的最短路径长度，除D[s]为0外，其余均为$\infty$；
循环：选择V\K中D[x]最小的x放入K中，对V\K中顶点y，若D[x]+w(x,y)小于D[y]，则更新D[y]为D[x]+w(x,y)，此时s到y的最短路径更新为(L(s,x),y)；
退出：V\K为空集；
如果图较稀疏，则可以将D实现为堆，每次删除根节点。
对于无环图，不必使用复杂的Dijkstra算法，而是以拓扑排序来选择顶点，具体如下。
初始：集合K包含已知最短路径的顶点，K初始为{s}，将s从图中删除；
循环：将刚刚从图中删除的顶点x的相邻顶点y删除并加入K，s到y的最短路径为(L(s,x),y)；
退出：V\K为空集；
关键路径
有向无环图更重要的一个问题是关键路径：对于一系列任务，可能一些任务之间存在依赖，根据这种依赖可生成对应的有向无环图；从最初的任务开始，可推算每个任务最早可以完成的时间；最后一个任务的最早完成时间就是整个项目的完成时间，也是最后一个任务最迟完成的时间；
以最后一个任务的最迟完成时间倒推，可推出每个任务最迟的完成时间；
对于一个任务(顶点)，若其最早完成时间与最迟完成时间相同，则称为零松弛顶点，由零松弛顶点组成的路径就是关键路径。
一个任务(顶点)的最早完成时间为所[依赖任务(顶点)的最早完成时间+该任务工期]的最大值；
一个任务(顶点)的最迟完成时间为[依赖它的任务的最迟完成时间-该任务工期]的最大值；