Member Avatar for logan_231_2009

Hello everyone, congratulations for the good job.
The last 5 days i search for a comprehensible and simple, CPM algorithm and i can't find one.
I want to make a program (in C++) that it will calculate the critical path of a given number of nodes..Any ideas? thanks for reading, and sorry for my English :)

Edited by logan_231_2009 because: n/a
  • 6 Contributors
  • 6 Replies
  • 3K Views
  • 3 Months Discussion Span
  • Latest Post Latest Post by user786

Dani AI

Generated

, by "critical path" in CPM we mean the longest-duration path through a precedence network (no cycles), i.e., the sequence of activities whose total time determines the project finish. In an Activity-on-Node (AON) model each task is a node with a duration; edges mean "must finish before." The graph must be a DAG. As asked, the key is to compute earliest and latest times: a forward pass to get ES/EF, then a backward pass to get LS/LF and slack. Tasks with zero slack form the critical path. Note: turning durations negative and running Dijkstra will not work because Dijkstra requires nonnegative weights; use a topological-order dynamic program (linear time) or, if you insist on sign-flipping, a shortest-path algorithm that tolerates negative weights. was right that this is a longest-path-in-a-DAG problem.

Minimal C++-style pseudocode for AON (durations on nodes):

// n tasks, dur[u], successors adj[u]
vector<int> indeg(n), topo, ES(n,0), EF(n,0), parent(n,-1);
for (int u=0; u<n; ++u) for (int v: adj[u]) ++indeg[v];

// Kahn topological sort
queue<int> q; for (int u=0; u<n; ++u) if (!indeg[u]) q.push(u);
while (!q.empty()) { int u=q.front(); q.pop(); topo.push_back(u);
  for (int v: adj[u]) if (--indeg[v]==0) q.push(v);
}
if ((int)topo.size()!=n) throw runtime_error("Precedence cycle found");

// Forward pass
for (int u: topo) {
  EF[u] = ES[u] + dur[u];
  for (int v: adj[u]) if (ES[v] < EF[u]) { ES[v] = EF[u]; parent[v] = u; }
}
int finish=-1, project_len=0;
for (int u=0; u<n; ++u) if (adj[u].empty() && EF[u] > project_len) { project_len=EF[u]; finish=u; }

// Backward pass for slack
const int INF=1e9; vector<int> LF(n,INF), LS(n), slack(n);
for (int u=0; u<n; ++u) if (adj[u].empty()) LF[u]=project_len;
for (int i=n-1; i>=0; --i) { int u=topo[i];
  if (!adj[u].empty()) { LF[u]=INF; for (int v: adj[u]) LF[u]=min(LF[u], LS[v]); }
  LS[u]=LF[u]-dur[u]; slack[u]=LS[u]-ES[u];
}
// Critical path: follow parent[] from 'finish' back while slack[u]==0

Tips:

  • Add a dummy Start (0 duration) linked to tasks with no predecessors, and a dummy Finish linked from tasks with no successors, to get a single critical path end.
  • Validate input: nonnegative durations, no cycles, and at least one start node. Complexity is O(V+E).

Recommended Answers

All 6 Replies

Member Avatar for mrnutty

Can you define what you mean by a critical path? Maybe give examples.

Member Avatar for sergent

What is an algorithm?

Member Avatar for logan_231_2009

Can you define what you mean by a critical path? Maybe give examples.

So...for example: http://www.brighthub.com/office/project-management/articles/49584.aspx

practically we had a number of jobs with their duration, and we want to discover the bigger in duration (in total) path. The reason is that we want to know how many works (and who) should not delay and this because then all project will delay..

example..
Duration of Path 2 = 0 days + 5 days + 3 days + 1 days + 8 days + 0 days = 17 days

Duration of Path 3 = 0 days + 5 days + 3 days + 4 days + 4 days + 6 days + 8 days + 8 days + 0 days = 38 days

Member Avatar for mike_2000_17

I may be wrong here, but isn't the CPM simply solved by formulating the problem as an Action-On-Arc (AOA) graph. Then, you just solve for the solution using a standard shortest-path algorithm (evidently, you multiply the costs by -1 to get a longest-path algorithm). You can, for instance, use the Boost Graph Library which includes several shortest-path algorithms including Dijkstra, A*, Bellman-Ford, etc. You can even export to Graphviz and get a visualization of the graph.

Member Avatar for user786

Learn more about Critical Path Method With Example, here:

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.