您的位置: 首页 > 文章 > 图：关键路径和最短路径 图：关键路径和最短路径 分类: 文章 • 2024-01-20 22:41:52 文章目录 关键路径 最短路径 关键路径 顶点是事件i和事件j，边的权值是活动所需的时间 例子： 第一步：确定哪些活动是关键活动（最早开始时间等于最晚开始时间） 第二步：确定哪些路径是关键路径（关键活动构造的路径） 最短路径 因为v6无法到达v5，所以v1到v5的最短路径就是21。 将每一顶点当作源点，依次调用迪杰斯特拉算法，同样可以得到每一对顶点之间的最短路径，事件复杂度Ｏ(n ^ 3)。 下面的弗洛伊德算法尽管也是Ｏ(n ^ 3)，但效率要比迪杰斯特拉算法高一些。
