Topological sort of minimum costs to finish interdependent tasks

Question

The problem that I'm trying to solve goes like this:

A project is split into tasks. Each task takes a known number of days. Some tasks can be done at any time(lets call these simple tasks), others depend on other tasks that must first be done. Design an algorithm that can find the minimum number of days necessary to finish the project.

I modeled each task as a node in a graph, and an edge from $x$ to $y$ means that task $y$ depends on task $x$. I also added a $0$ node. Edges go from $0$ to all of the free nodes.

I proceeded to implement Kruskal, with some modifications to deal with the task dependency problem. After banging my head against the keyboard for a while, I realized Kruskal doesn't work on directed graphs.

I did some reading and stumbled upon the topological sort, which seemed to be just what I needed for my problem. While topological sort itself is nice and simple, and I can easily find a topological sort of my graph, I can't figure out how to find the one of minimum cost(cost being number of days, of course).

An idea that just came to me is introducing another new node, call it $-1$. All other nodes have edges going to this one, of $0$ cost. This would be the finish node, and now the problem becomes finding the minimum path from $0$ to $-1$, that is also a topological sort.

Any hints are very much appreciated!

Answer 1

I am assuming here that you are allowed to start tasks in parallel if there is no dependency between them, otherwise I think that no matter what order you do, the total time needed to finish the project will always be the same.

Let $t_i$ represent a task and a vertex in your dependency graph. Let $d[t_i]$ be the days needed to complete task $t_i$ and $f[t_i]$ be the actual time $t_i$ is accomplished (finish time). Initially, $f[t_i] = d[t_i]$ for all tasks. Let $F$, initially 0, be the maximum finish time. The solution is as follows:

1. Perform the topological sort of the dependency graph to obtain the sequence $T$.
2. Visit each vertex according to their order in $T$:
   1. Let $t_i$ be the current vertex. If $f[t_i] > F$, then $F= f[t_i]$.
   2. If $(t_i,t_j)$ is an edge (meaning $t_j$ is dependent to $t_i$) and $f[t_j] \lt f[t_i] + d[t_j]$ then update $f[t_j] = f[t_i] + d[t_j]$.
3. Finally, return $F$.

The idea for step 2.2 is to compute the finishing time of a task with respect to the finishing time of its dependency. When a task has multiple dependencies, its finish time will be based on the time of the dependency that will finish late.

Note: I think that this solution is the iterative, bottom-up version of John L.'s solution.

Answer 2

This problem is basically to find the longest path in a directed acyclic graph (DAG).

---

Let $cost[t]$ be the number of days it takes to do task $t$.
Let $m[t]$ be the minimum number of days to finish task $t$ and all its prerequisite tasks.
Let $prerequisite[t]$ be the set of prerequisite tasks for task $t$.

We have the following recurrence relation. $$m[t] = cost[t] + \max_{p\in prerequisite[t]}m[p]$$

The minimum number of days necessary to finish the project is $\max_v m[v]$, where $v$ ranges over all tasks.

---

Here is an implementation in Python.

from functools import cache

def min_days_to_finish_project(cost, prerequisite):
    @cache
    def min_days_to_finish_task(t):
        return cost[t] + max((min_days_to_finish_task(p) for p in prerequisite[t]),
                             default=0)

    return max(min_days_to_finish_task(t) for t in cost)

# Example
c = {1: 5, 2: 8, 3: 13}  # tasks are [1, 2, 3]
pre = {1: [], 2: [], 3: [1, 2]}
print(min_days_to_finish_project(c, pre))  # 21

---

It is assumed above that the project can be completed, i.e., there is no circular dependencies. Otherwise, we should check that first.