algorithm - 按到端节点的距离对图进行排序

Question

我有一个属于图表的节点列表。该图是有向的，不包含循环。此外，一些节点被标记为“结束”节点。每个节点都有一组我可以使用的输入节点。

问题如下:如何按到任何可达端节点的最大距离对列表中的节点进行排序(升序)？这是图表的外观示例。

我已经添加了计算的距离，之后我可以对节点进行排序(灰色)。末端节点的距离为 0，而 C、D 和 G 的距离为 1。但是，F 的距离为 3，因为通过 D 的方法会更短 (2)。

我做了一个我认为的概念，问题就解决了。这是一些伪代码:

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++;
}

这种方法应该有效。然而，该算法的问题在于它基本上是从基于每个端节点的图形创建树，然后为每个深度更正旧的距离计算。例如:G 的深度为 1(直接在 B 上计算)，然后是深度 3(在 A、D 和 F 上计算)，然后是深度 4(在 A、C、E 和 F 上计算)。

对于这个问题，你有更好的解决方案吗？

Answer 1

可以用dynamic programming来完成.

图表是DAG , 所以先做一个 topological sort在图表上，令排序顺序为 v1,v2,v3,...,vn。

现在，为所有“端节点”设置D(v)=0，并从最后到第一个(根据拓扑顺序)执行:

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

之所以有效，是因为该图是一个 DAG，当以相反的拓扑顺序完成时，所有输出边 (v,u)< 的所有 D(u) 的值 是已知的。

---

图表示例:

拓扑排序(一种可能):

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

然后，算法:

init: 

D(B)=D(A)=0

从最后回到第一个:

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

---

作为旁注，如果图不是 DAG，而是一般图，这是 Longest Path Problem 的变体，这是 NP 完全的。
幸运的是，当我们的图是 DAG 时，它确实有一个有效的解决方案。