Search algorithm for all critical paths

Question

I need to create an algorithm that could find all critical paths in a graph.

I found the topological order of the nodes, calculated the earliest end times and last start times for each node.

I also found all the critical nodes (i.e. those that are on the critical path).

The problem is to put it all together and actually print all of these paths. If there is only one critical path in the graph, I can handle it, but problems begin if there are several paths.

For example, one node is part of several critical paths, several start nodes, several end nodes, etc. I could not find an algorithm that could take all these factors into account.

The result I'm looking for is something like this (if a, b, c, etc. are all nodes):

• a-> e
• a-> C-> F-> I-> J-> k
• a-> C-> g
• l-> e

It would be nice if someone could write a description of the algorithm, which could find ways from knowledge of critical nodes, topological order, etc. Or maybe also in C or java code.

EDIT: Here is an example that should provide the output I posted earlier. Critical tracks are red, the values ​​of each node are marked above or next to it.

Answer 1

Calculating the last initial values ​​almost provides a critical path. You need to build the results from the terminal nodes and go back:

• find all nodes that have the maximum early end time (m = 11, nodes = {e, r, k})
• , .   e l k t = 2, l- > e, a- > e. g, t = 6, node c,   c- > g. k, t = 10, j , j- > k.
• , node. l- > e a- > e - .  c- > g a, a- > c- > g. j- > k t = 9, ,   i- > j- > k.

Answer 2

: ? : Dijkstra - , , .