a. Problem Analysis
In the Critical Path Method (CPM), we need to identify the critical path in a project, which is the sequence of activities that determines the project’s total duration. To solve this problem, we first construct a data structure Activity to represent project activities and design a Project class to handle project calculations and output.
The calculation of the critical path primarily relies on two key steps:
- Earliest Start Time (ES) Calculation: Starting from the initial event, we use topological sorting and dynamic programming to compute the earliest start time for each activity.
- Latest Start Time (LS) Calculation: Starting from the final event, we perform a reverse traversal of the topological order and use dynamic programming to compute the latest start time for each activity.
By comparing the earliest and latest start times, we can identify the activities on the critical path, which are crucial for determining the project’s total duration.
b. Algorithm Design
1. Calculating Earliest Start Time
We use topological sorting and dynamic programming to compute the earliest start time. First, we identify all initial events (activities with no predecessors) and then traverse the graph starting from these events, updating the earliest start time for each activity.
// Calculate earliest start time
void calculateEarliestStart() {
queue<int> q;
for (const Activity& activity : activities) { // Traverse topological order
if (activity.next.empty()) { // If a node's adjacency list is empty (i.e., it's an initial event)
q.push(activity.id); // Enqueue
earliestStart[activity.id] = 0; // Set earliest start time to 0
}
}
while (!q.empty()) { // While queue is not empty
int currentId = q.front(); // Dequeue the highest-priority event (currentId)
q.pop();
for (int nextId : activities[currentId].next) { // Traverse currentId's adjacency list
earliestStart[nextId] = max(earliestStart[nextId], earliestStart[currentId] + activities[currentId].duration);
// nextId's earliest start time = max{current recorded earliest start time, predecessor currentId's earliest start time + currentId's duration}
q.push(nextId);
}
}
}
2. Calculating Latest Start Time
By traversing the topological order in reverse, we compute the latest start time. Starting from the final event, we iteratively update the latest start time for each activity.
// Calculate latest start time
void calculateLatestStart() {
latestStart = earliestStart; // Initialize latest start time as earliest start time
for (int i = activities.size() - 1; i >= 0; --i) { // Reverse traversal starting from the last event (i)
for (int nextId : activities[i].next) {
latestStart[i] = min(latestStart[i], latestStart[nextId] - activities[i].duration);
// Current event's latest start time = min{recorded latest start time, next event nextId's latest start time - current event i's duration}
}
}
}
c. Data Structure Design
We use two key data structures:
ActivityStruct: Represents a project activity, including the activity ID, duration, and subsequent activities.
// Struct representing a project activity
struct Activity {
int id; // Activity ID
int duration; // Duration
vector<int> next; // Subsequent activities
};
ProjectClass: Manages the project, including methods for adding activities, calculating earliest and latest start times, printing the critical path, and displaying time information.
d. Debugging Process
During debugging, we focused on the following aspects:
- Data Structure Correctness: Ensuring the
Activitystruct andProjectclass accurately represent project and activity relationships. - Algorithm Correctness: Verifying the correctness of the algorithms for calculating earliest and latest start times.
- Output Accuracy: Checking if the printed critical path and time information meet expectations.
e. Output Results
After running the program, we obtained the following output:
Critical Path: 0 1 2 3 4 5
Activity 0: ES=0, LS=0
Activity 1: ES=2, LS=2
Activity 2: ES=6, LS=6
Activity 3: ES=9, LS=9
Activity 4: ES=14, LS=14
Activity 5: ES=16, LS=16
From the results, we can see that the critical path consists of activities 0, 1, 2, 3, 4, and 5. The earliest and latest start times for each activity are correctly calculated, confirming the effectiveness of our algorithm and data structure design.
f. Source Code
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
// Struct representing a project activity
struct Activity {
int id; // Activity ID
int duration; // Duration
vector<int> next; // Subsequent activities
};
class Project {
private:
vector<Activity> activities; // Vector storing project activities
vector<int> earliestStart; // Earliest start time
vector<int> latestStart; // Latest start time
public:
// Add an activity
void addActivity(int id, int duration, const vector<int>& next) {
activities.push_back({id, duration, next});
}
// Calculate earliest start time
void calculateEarliestStart() {
queue<int> q;
for (const Activity& activity : activities) { // Traverse topological order
if (activity.next.empty()) { // If a node's adjacency list is empty (i.e., it's an initial event)
q.push(activity.id); // Enqueue
earliestStart[activity.id] = 0; // Set earliest start time to 0
}
}
while (!q.empty()) { // While queue is not empty
int currentId = q.front(); // Dequeue the highest-priority event (currentId)
q.pop();
for (int nextId : activities[currentId].next) { // Traverse currentId's adjacency list
earliestStart[nextId] = max(earliestStart[nextId], earliestStart[currentId] + activities[currentId].duration);
// nextId's earliest start time = max{current recorded earliest start time, predecessor currentId's earliest start time + currentId's duration}
q.push(nextId);
}
}
}
// Calculate latest start time
void calculateLatestStart() {
latestStart = earliestStart; // Initialize latest start time as earliest start time
for (int i = activities.size() - 1; i >= 0; --i) { // Reverse traversal starting from the last event (i)
for (int nextId : activities[i].next) {
latestStart[i] = min(latestStart[i], latestStart[nextId] - activities[i].duration);
// Current event's latest start time = min{recorded latest start time, next event nextId's latest start time - current event i's duration}
}
}
}
// Print the critical path
void printCriticalPath() {
cout << "Critical Path: ";
for (const Activity& activity : activities) { // Traverse topological order
if (earliestStart[activity.id] == latestStart[activity.id]) { // Critical path activities have ES == LS
cout << activity.id << " ";
}
}
cout << endl;
}
// Print earliest and latest start times
void printTimeInfo() {
for (const Activity& activity : activities) {
cout << "Activity " << activity.id << ": ES=" << earliestStart[activity.id]
<< ", LS=" << latestStart[activity.id] << endl;
}
}
// Constructor for initialization
Project(int numActivities) : earliestStart(numActivities), latestStart(numActivities) {}
};
int main() {
Project project(6); // Assume there are 6 activities
// Add activities in the format: activity ID, duration, subsequent activity IDs
project.addActivity(0, 2, {1});
project.addActivity(1, 4, {2});
project.addActivity(2, 3, {3});
project.addActivity(3, 5, {4});
project.addActivity(4, 2, {5});
project.addActivity(5, 1, {});
// Calculate earliest and latest start times
project.calculateEarliestStart();
project.calculateLatestStart();
// Print critical path and time information
project.printCriticalPath();
project.printTimeInfo();
return 0;
}
When will I have a drink and discuss the details again?