10.1 最短通路

• 设 是带权有向图，对每条弧 指定一个非负实数的权 ，若 ，则令 。称 为弧 的长度。
• 通路 的长度：在带权有向图中，通路 中各弧长度之和称为通路 的长度 。
• 最短通路：在带权有向图中，从顶点 到 的通路中长度最小者称为从 到 的最短通路，并称其长度为从 到 的距离 。

10.2 关键通路

• 工序流线图是满足以下条件的简单带权有向图：

  • 没有回路。
  • 有唯一的引入次数为 0 的顶点，称其为发点。
  • 有唯一的引出次数为 0 的顶点，称其为收点。
  • 每个顶点都在某条从发点到收点的通路上。
  • 每条弧的权是非负实数。

• 最早完成时间：在工序流线图中，从发点 到事件 的最长通路的长度称为事件 的最早完成时间，记为 。
  
  
  

• 最迟完成时间：给定工序流线图，在保证收点 的最早完成时间不增加的前提下，自发点 最迟到达事件 的时间称为 的最迟完成时间，记为 。
  
  
  

• 关键通路：在工序流线图中，从发点到收点的最长通路称为关键通路。

• 事件 在某条关键通路上当且仅当它的最早完成时间和最迟完成时间相等。

• 缓冲时间：给定工序流线图 ，，定义 的缓冲时间 。

  • 事件 的发生可以比预定的最早完成时间推迟缓冲时间 ，而不会影响整个工程的进度。
  • 关键通路上的所有事件的缓冲时间都是0，即它们都要准时发生，不能推迟，并且关键通路上的工序都要按时完成，不能推迟。