1
$\begingroup$

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!

$\endgroup$
5
  • $\begingroup$ Where did you encounter this task? Can you credit the original source, or describe the motivation? $\endgroup$
    – D.W.
    Jun 5, 2022 at 2:31
  • 1
    $\begingroup$ I would assume that you are allowed to do multiple tasks on the same day as long as there is no dependency between them, right? $\endgroup$
    – Russel
    Jun 5, 2022 at 3:06
  • $\begingroup$ @Wolfuryo Topological sort is useful here indeed. Although task $0$ and task $-1$ are not necessary, it is nice to imagine that they stand for the start and the end of the project. $\endgroup$
    – John L.
    Jun 5, 2022 at 6:28
  • $\begingroup$ @D.W. The problem was given a few years ago in an exam that I'm preparing for. The course is on trees and graphs. Russel, the problem doesn't say. I assumed you can only complete one task at a time. $\endgroup$
    – Wolfuryo
    Jun 5, 2022 at 9:25
  • 1
    $\begingroup$ Great! I encourage you to credit the source and the author who wrote that exam. $\endgroup$
    – D.W.
    Jun 5, 2022 at 20:00

2 Answers 2

3
$\begingroup$

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.

$\endgroup$
1
  • 1
    $\begingroup$ Hmm, you're right, if tasks can't be started in parallel, then since all of them have to be done, obviously the minimum time will just be the sum of each individual times. Thanks for the help! $\endgroup$
    – Wolfuryo
    Jun 5, 2022 at 11:35
3
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Thank you! I'll go through the code later today! $\endgroup$
    – Wolfuryo
    Jun 5, 2022 at 9:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.