sort graph by distance to end nodes

Question

I have a list of nodes which belong in a graph. The graph is directed and does not contain cycles. Also, some of the nodes are marked as "end" nodes. Every node has a set of input nodes I can use.

The question is the following: How can I sort (ascending) the nodes in the list by the biggest distance to any reachable end node? Here is an example off how the graph could look like.

I have already added the calculated distance after which I can sort the nodes (grey). The end nodes have the distance 0 while C, D and G have the distance 1. However, F has the distance of 3 because the approach over D would be shorter (2).

I have made a concept of which I think, the problem would be solved. Here is some pseudo-code:

sortedTable<Node, depth> // used to store nodes and their currently calculated distance
tempTable<Node>// used to store nodes 
currentDepth = 0;

- fill tempTable with end nodes

while( tempTable is not empty)
{

    - create empty newTempTable<Node node>

    // add tempTable to sortedTable
    for (every "node" in tempTable)
    {
        if("node" is in sortedTable)
        {
            - overwrite depth in sortedTable with currentDepth
        }
        else 
        {
            - add (node, currentDepth) to sortedTable
        }

        // get the node in the next layer
        for ( every "newNode" connected to node)
        {
            - add newNode to newTempTable
        }

        - tempTable = newTempTable  
    }
    currentDepth++;
}

This approach should work. However, the problem with this algorithm is that it basicly creates a tree from the graph based from every end node and then corrects old distance-calculations for every depth. For example: G would have the depth 1 (calculatet directly over B), then the depth 3 (calculated over A, D and F) and then depth 4 (calculated over A, C, E and F).

Do you have a better solution to this problem?

Answer 1

It can be done with dynamic programming.

The graph is a DAG, so first do a topological sort on the graph, let the sorted order be v1,v2,v3,...,vn.

Now, set D(v)=0 for all "end node", and from last to first (according to topological order) do:

D(v) = max { D(u) + 1, for each edge (v,u) }

It works because the graph is a DAG, and when done in reversed to the topological order, the values of all D(u) for all outgoing edges (v,u) is already known.

---

Example on your graph:

Topological sort (one possible):

H,G,B,F,D,E,C,A

Then, the algorithm:

init: 

D(B)=D(A)=0

Go back from last to first:

D(A) - no out edges, done
D(C) = max{D(A) + 1} = max{0+1}=1
D(E) = max{D(C) + 1} = 2
D(D) = max{D(A) + 1} = 1
D(F) = max{D(E)+1, D(D)+1} = max{2+1,1+1} = 3
D(B) = 0
D(G) = max{D(B)+1,D(F)+1} = max{1,4}=4
D(H) = max{D(G) + 1} = 5

---

As a side note, if the graph is not a DAG, but a general graph, this is a variant of the Longest Path Problem, which is NP-Complete.
Luckily, it does have an efficient solution when our graph is a DAG.