跳转至

9. Floyd和AOE网

阅读信息

约 458 个字  2 分钟  本页总访问量：加载中... 次

🌌Class Nine

所有点对的最短路径(All-Pairs Shortest Paths)

一点出发到其他点的最短路径：算一行（n 个值） 所有点对的最短路径(All-Pairs Shortest Paths)：算一个矩阵（n*n 矩阵）

动态规划： 大问题分解为小问题。在某些场景下，分治法或递归时小问题可能重复计算，效率低（分治法是 top-down，从上到下计算）。 动态规划为 botton-up，先求基础解再求高层解。基础解可能有很多，需要用数组等结构存储。 分析问题的思路是 top-down，解答问题的流程是 botton-up。

动态规划实现最短路径问题： D(i,j)表示 vi 出发到 vj 为最短路径，中间可能经过点集。 如果中间不经过任何点（为空集），答案为边长。 如果允许经过 v1 这个点，分为 vi 到 vj，和 vi 到 v1 再 v1 到 vj（这两段之间都是空集）。 如果允许经过 v1，v2 两个点，分为 vi 允许经过 v1 到 vj，和 vi 允许经过 v1 到 v2 再允许经过 v1 到 vj。

Floyd 初始化：边或无穷大 状态转移：允许经过点 基本框架:

C
1
2
3
4
5
for (中转点k)
    for (起点i)
        for (终点j)
        //判断是否更新
        d[i][j]=min(d[i][j],d[i][k]+d[k][j]);

AOE 网(Activity On Edge)

从一个点出发有多个任务可以做。一个节点表示时间点，所有入边的任务都完成后才能做节点以后的任务。 为什么找关键路径？如果要把时间缩短，需要加快哪些任务才能使整体时间减少。 最早完成时间：所有之前的支路所需时间的最大值 可能建立 dummy activity（所需时间为 0），建立不同任务之间的关联。

EC(Early Complete time)：max{所有入点的 EC + 入边的时间} （表示每个任务最少多长时间才能到达） LC(Last Complete time)：min{所有出点的 LC - 出边的时间} （表示每个任务能偷懒多长时间，最晚什么时候出发） 如果节点的 EC == LC，该点是关键点。关键点组成关键路径。