最小生成树
生成树
71.png
72.png
最小生成树
73.png
74.png
75.png
76.png
77.png
78.png
最小生成树可能不唯一
79.png
最短路径
80.png
81.png
1一个顶点到其他顶点的最短路径算法
82.png
所有顶点间最短路径
1对每个顶点重复算法1
2Floyd算法 O(n³)
83.png
84.png
拓扑排序
85.png
86.png
AOV解决拓扑排序；AOE解决关键路径
87.png
88.png
89.png
90.png
91.png
关键路径
用AOE网表示关键路径
92.png
93.png
94.png
求解关键路径
95.png
96.png
97.png
98.png
最早发生时间（左）和最晚发生时间（右）举例：
99.png
100.png
ve是顶点i的最早发生时间，当有多个入口时，选和最大的一条（类似课程，需要把基础都学完才能学下一门）
vl是顶点i的最晚发生时间，算完所有的ve后，从终点往回算，如上面从18开始往回推，（如果要在第18天完成，则上一条最晚在多少天开始学，当有多个来源时取最小的）
e是活动最早开始时间。（理解：把之前基础课都学完才能学下一门，所以有多条入口时，是取得最大的，也就是ve）
l代表最晚什么时候开始学才能赶上最终进度。
l-e = 0的为关键节点（一天也晚不了）从而求出关键路径！！！
101.png
网友评论