void graph::weightednegativevertex queue qfor each vertex dist infinitys dist enqueues )while! isemptyvertex dequeue)for each vertex adjacent to ifv dist cvw dist /update dist dist cvww path vifw is not already in enqueuew )figure pseudocode for weighted shortest-path algorithm with negative edge costs application might be the modeling of (nonreversiblechemical reactions we could have each vertex represent particular state of an experiment edges would represent transition from one state to anotherand the edge weights might represent the energy released if only transitions from higher energy state to lower are allowedthe graph is acyclic more important use of acyclic graphs is critical path analysis the graph in figure will serve as our example each node represents an activity that must be performedalong with the time it takes to complete the activity this graph is thus known as an activity-node graph the edges represent precedence relationshipsan edge (vwmeans that activity must be completed before activity may begin of coursethis implies that the graph must be acyclic we assume that any activities that do not depend (either directly or indirectlyon each other can be performed in parallel by different servers this type of graph could be (and frequently isused to model construction projects in this casethere are several important questions which would be of interest to answer firstwhat is the earliest completion time for the projectwe can see from the graph that time units are required along the path acfh another important question is to determine which activities can be delayedand by how longwithout affecting the minimum completion time for instancedelaying any of acfor would push the completion