第六章 图的应用

基础概念

相关提炼内容见 graph。

最小生成树 MST

• Prim 算法见 prim
• Kruskal 算法见 kruskal

最短路径

• Dijkstra 算法见 dijkstra——求单源最短路径问题
  • 迪杰斯特拉 Dijkstra
    • Dijkstra 算法
• Floyd 算法——求各顶点之间最短路径问题
• ~OSPF 算法
• ~SPFA 算法 Shortest Path Faster Algorithm

有向无环图描述表达式

• 有向无环图 Direct Acyclic Graph

拓扑排序

见 topological-sort。

关键路径

• 事件 v_k 的最早发生时间 ve(k)
• 事件 v_k 的最迟发生时间 vl(k)
• 活动 a_i 的最早开始时间 e(i)
• 活动 a_i 的最迟开始时间 l(i)
• 一个活动 a_i 的最迟开始时间 l(i)和其最早开始时间 e(i)的差额 d(i)=l(i)-e(i)