Critical Path Analysis

This program implements the PERT/CPM (Program Evaluation and Review Technique / Critical Path Method) algorithm for project network analysis. It accepts user-defined events (tasks) and activities (durations between events), storing the network in a two-dimensional array T(M,M) where M is the number of events. The forward pass computes earliest event times in array E(), and the backward pass computes latest allowable times in array L(); events where E(I) equals L(I) lie on the critical path. Dummy activities (zero-duration logical dependencies) are handled via a subroutine at line 500, which initializes unused matrix cells to the sentinel value 99999999 to distinguish them from real zero-duration entries.

Program Analysis

Program Structure

The program is organized into a main flow with two subroutines:

1. Lines 1–70: Splash screen and data entry — collects M (number of events), N (number of activities), and the time matrix T(M,M) via prompted INPUT loops.
2. Lines 75–205: Forward pass — computes earliest event times E(I) for all events I from 2 to M.
3. Lines 206–301: Backward pass — computes latest allowable times L(I) for all events from M−1 down to 1.
4. Lines 310–390: Output — prints events where L(I)−E(I) = 0 (critical path nodes), with their latest completion times.
5. Lines 500–630: Subroutine — initializes the T matrix sentinel values and optionally collects dummy activity definitions.
6. Lines 2000–2080: Subroutine — title splash screen, waits for ENTER before returning.

Data Structures

The adjacency matrix T(M,M) is the central data structure. Because BASIC initializes numeric arrays to zero, the subroutine at line 500 scans all cells and replaces any zero with the sentinel value 99999999 to indicate “no arc.” Dummy activities (zero-duration logical links) are then re-entered as genuine zeros after this initialization step, allowing the algorithm to distinguish a real zero-time dependency from an absent arc.

• T(M,M) — adjacency/weight matrix for the project network
• E(M) — earliest event time array (forward pass result)
• L(M) — latest event time array (backward pass result)

Algorithm Details

The forward pass (lines 100–205) iterates events in topological order (assumed to be numeric order 1..M). For each event I, it first finds any predecessor J with a real arc and seeds E(I), then checks all predecessors to find the maximum of T(J,I)+E(J). This two-phase inner loop (lines 101–104 for seeding, lines 140–200 for maximizing) is a workaround for not being able to initialize E(I) to −∞ before the loop.

The backward pass (lines 210–301) mirrors this logic in reverse, seeding L(I) from the first successor found and then minimizing over L(J)−T(I,J) for all successors J. L(M) is initialized to E(M) at line 206, fixing project completion time.

Critical path events are identified at output time (lines 320–380): any event where E(I) = L(I) (i.e., zero total float) is printed.

Key BASIC Idioms and Techniques

• The sentinel value 99999999 is used throughout to represent “no arc,” a common sparse-matrix trick in integer BASIC where a dedicated boolean array would be expensive.
• FAST / SLOW (lines 75 and 310) bracket the computation to maximize calculation speed while restoring display output mode for results.
• Input confirmation loop (lines 30–33) uses IF Y$<>"Y" THEN GOTO 20 to re-prompt on any non-Y response, a simple but effective validation pattern.
• The variable K is used to count dummy activities; it is initialized to 0 at line 8. The checks at lines 331 and 335 (IF K>=18) attempt scroll management, but since K is repurposed to count dummies and is not updated during the output loop, this guard does not correctly track screen lines.
• The counter K1 (line 311) counts critical-path events but is never used or printed — it is vestigial.

Bugs and Anomalies

Input Assumptions

The algorithm assumes events are numbered 1..M in strict topological order (no back-arcs). Activity times are entered as individual event-pair connections with a confirmation prompt. The program explicitly warns users not to guess activity counts and not to include dummy activities in the initial N count, collecting dummies separately via the subroutine at line 500.

   1 GOSUB 2000
   2 PRINT "PERT-CPM FINDS THE CRITICAL PATHIN THE PROJECT NETWORK. EVENTS  ARE TASKS AND TIMES BETWEEN     EVENTS ARE ACTIVITIES. "
   3 GOSUB 2060
   4 CLS
   5 PRINT "ENTER NUMBER OF EVENTS(TASKS)   YOU NEED TO PERFORM"
   6 INPUT M
   7 CLS
   8 LET K=0
  10 PRINT "ENTER NUMBER OF ACTIVITIES      (TIMES BETWEEN EVENTS) YOU NEED"
  11 PRINT AT 10,0;"YOU SHOULD NOT BE GUESSING"
  12 PRINT "DO NOT INCLUDE DUMMY ACTIVITIES"
  13 INPUT N
  15 CLS
  17 DIM T(M,M)
  18 FOR I=1 TO N
  20 PRINT "ENTER AN EVENT "
  21 INPUT O
  22 PRINT O
  23 PRINT "ENTER THE EVENT ";O;" PRECEDES"
  24 INPUT P
  25 PRINT P
  27 PRINT "EVENT ";O;" PRECEDES EVENT ";P
  29 PRINT 
  30 PRINT "ABOVE CORRECT ?  Y/N"
  31 INPUT Y$
  33 IF Y$<>"Y" THEN GOTO 20
  34 PRINT 
  35 PRINT "THE TIME FROM EVENT ";
  40 PRINT " ";O;
  45 PRINT "           TO EVENT ";
  50 PRINT P;" ";
  55 PRINT "IS ?"
  60 INPUT T(O,P)
  65 CLS
  70 NEXT I
  75 FAST
  80 DIM E(M)
  90 DIM L(M)
  91 GOSUB 500
 100 FOR I=2 TO M
 101 FOR J=1 TO I
 102 IF T(J,I)<>99999999 THEN LET E(I)=T(J,I)+E(J)
 103 IF T(J,I)<>99999999 THEN GOTO 140
 104 NEXT J
 140 FOR J=1 TO I
 145 IF T(J,I)=99999999 THEN GOTO 200
 150 IF T(J,I)+E(J)<=E(I) THEN GOTO 200
 160 LET E(I)=T(J,I)+E(J)
 200 NEXT J
 205 NEXT I
 206 LET L(M)=E(M)
 210 FOR I=M-1 TO 1 STEP -1
 211 FOR J=I TO M
 212 IF T(I,J)<>99999999 THEN LET L(I)=L(J)-T(I,J)
 213 IF T(I,J)<>99999999 THEN GOTO 217
 214 NEXT J
 217 FOR J=I TO M
 220 IF T(I,J)=99999999 THEN GOTO 300
 230 IF L(J)-T(I,J)>=L(I) THEN GOTO 300
 240 LET L(I)=L(J)-T(I,J)
 300 NEXT J
 301 NEXT I
 310 SLOW
 311 LET K1=0
 312 PRINT "CRITICAL";
 313 PRINT TAB 22;"LATEST"
 314 PRINT "PATH";
 315 PRINT TAB 22;"COMPLETION"
 316 PRINT TAB 22;"TIME"
 320 FOR I=1 TO M
 321 IF E(I)-L(I)=0 THEN LET K1=K1+1
 330 IF L(I)-E(I)=0 THEN PRINT "  ";I;
 331 IF K>=18 AND L(I)-E(I)=0 THEN SCROLL
 334 IF L(I)-E(I)=0 THEN PRINT TAB 25;L(I)
 335 IF K>=18 AND L(I)-E(I)=0 THEN SCROLL
 380 NEXT I
 390 STOP
 500 FOR I=1 TO M
 505 FOR J=1 TO M
 510 IF T(I,J)=0 THEN LET T(I,J)=99999999
 520 NEXT J
 530 NEXT I
 540 PRINT "ENTER YES IF THERE ARE" 
 550 PRINT "DUMMY ACTIVITIES"
 560 PRINT "ENTER NO IF THERE ARE NONE"
 565 INPUT A$
 566 CLS
 570 IF A$="NO" THEN RETURN
 575 PRINT "HOW MANY ?"
 580 INPUT K
 585 CLS
 590 FOR I=1 TO K
 600 PRINT "DUMMY ACTIVITY"
 605 PRINT "IS FROM ?   TO ?"
 606 INPUT A
 607 PRINT A
 610 INPUT B
 615 LET T(A,B)=0
 620 CLS
 625 NEXT I
 630 RETURN
 631 SAVE "PERT-CP[M]"
 632 CLS
 635 GOTO 1
 2000 REM 
 2005 SLOW
 2010 CLS
 2020 PRINT AT 10,10;"TS1000"
 2030 PRINT AT 11,3;"CRITICAL PATH ANALYSIS"
 2040 PRINT 
 2050 PRINT AT 13,9;"PERT-CPM"
 2060 PRINT AT 21,0;"PRESS ENTER WHEN READY"
 2070 INPUT Y$
 2075 CLS
 2080 RETURN