**Order-requirement networks**

An *order-requirement network* is a weighted digraph, or network, that has these characteristics:

It contains two special vertices, the starting vertex and the terminating vertex. They are usually designated byOrder-requirement networks are used primarily to represent sets of tasks that make up a job. The tasks are represented by vertices; an arrow from one vertex to another represents the fact that the task represented by the first vertex must be completed before the task represented by the second vertex can be started. For that reason, in an order-requirement network, if a directed edge points from vertexSandT. These vertices are sometimes also called thesourceand thesink.No edges end at the source; no edges begin at the sink. In other words, the indegree of the source and the outdegree of the sink are 0.Every vertex in the network is on a (directed) path from

StoT.

A *critical path* of the network is a path of greatest length from *S* to *T.* The length of this path is called the *earliest finish time,* or EFT, of the network. The *Critical Path Method,* or CPM, is an algorithm for finding a critical path of an order-requirement network. It relies on finding the length of the longest path from *S* to each vertex. That length is known as the *EFT of the vertex.*

Copyright © 1999-2000 SciMathMN