ABSTRACT
Network analysis provides a framework for the study of a special class of linear programming problems that can be modeled as network programs. This chapter begins with some basic definitions and properties of graphs and networks. The shortest path problem can be viewed as a transshipment problem having a single source and a single destination. There are several well-known algorithms for finding the shortest path between certain pairs of nodes in a network. The chapter concentrates first on a particularly simple algorithm that is based on the use of recursive computations. Dynamic programming is an approach to solving mathematical programming problems by decomposing a problem into simpler, interdependent, subproblems, and then finding solutions to the subproblems in stages, in such a way that eventually an optimal solution to the original problem emerges. A project network provides a graphical representation of the precedence relations among all the activities in a project. Each activity is represented by an arc in the network.
