给定一个 DAG，最长路径的长度和它结束的节点，我如何追溯我的步骤以便打印最长路径的每个节点？

Question

我正在研究一个问题，即在给定平行六面体列表的情况下，找到最多可以相互存储的平行六面体。

我的方法是用邻接表来表示图，进行拓扑排序，然后为拓扑数组中的每个节点“松弛”边，给我最长的路径。

下面是代码，但我认为这对问题不重要。

typedef struct Edge {
int src;            /* source node  */
int dst;            /* destination node  */
struct Edge *next;
} Edge;


int maxend;  //node in which the longest path ends
int mp; // longest path

for (int i = 0; i < G.n; i++)
{   
    int j = TA[i];             //TA is the topological sorted array
    if (g->edges[j] != NULL) 
    {                           
        if(DTA[j] == -1) DTA[j] = 0; 
        
        Edge* tmp = G.edges[j];
    
        while (tmp != NULL)
        {   
            if(DTA[tmp->src] >= DTA[tmp->dst]){     //DTA is the array that keeps track of the maximum distance of each node in TA
                DTA[tmp->dst] = DTA[tmp->src]+1;   
                if (DTA[tmp->dst] > mp) {
                    mp = DTA[tmp->dst];
                    maxend = tmp->dst;
                }
            }    
            tmp = tmp->next;
        }
    }
}

最后我得到了最长路径的长度和所述路径结束的节点，但我如何有效地重新创建路径？

如果平行六面体A包含平行六面体B并且平行六面体B包含平行六面体C这意味着平行六面体A也是平行六面体盒子C，这意味着每条边的权重为1并且最长路径开始的顶点具有最长路径的最远节点他的邻接列表中的路径。

我想到了 3 个解决方案，但 none 个看起来很棒。

迭代权重为 0 的每个顶点的边（因此没有前任），如果有选择，请避免选择连接它与最远节点的边（如前所述，最短路径起始节点和结束节点之间将是 1)
在拓扑排序数组中跟踪每个节点最大距离的数组中：从代表我们找到的最远节点的索引开始，看前一个节点是否有兼容的距离（如in，前一个节点的距离比最远的节点少 1 个）。如果是这样，请检查它的邻接列表以查看最远的节点是否在其中（因为如果最远的节点距离为 10，则可能有几个距离为 9 但未连接到它的节点）。重复直到我们到达路径的根。
到目前为止最有可能的候选者，创建一个指针数组来跟踪每个节点的“最大”父节点。在上面的代码中，每当一个节点的最大距离发生变化时，这意味着它的父节点（如果有的话）比前一个父节点的距离更长，这意味着我们可以更改与当前节点关联的最大父节点。

编辑：我最终只是分配了一个新数组，每次更新节点的权重时（ DTA[tmp->src] >= DTA[tmp->dst] ）我还存储了源的编号目标边的单元格中的边。

Answer 1

我假设图边 u <- v 表示框 u 大到足以包含 v。

我建议你放弃拓扑排序。相反：

SET weight of every edge to -1
LOOP
   LOOP over leaf nodes ( out degree zero, box too small to contain others )
       Run Dijkstra algorithm ( gives longest path, with predecessors )
       Save length of longest path, and path itself
   SAVE longest path
   REMOVE nodes on longest path from graph
   IF all nodes gone from graph
        OUTPUT saved longest paths ( lists of nested boxes )
        STOP

这称为“贪心”算法。不能保证提供最佳结果。但它又快又简单，总是给出合理的结果，而且经常给出最优结果。

Answer 2

I think this solves it，除非有什么不明白的。

如果使边权重为负，则 DAG 中权重最高的路径等效于权重最低的路径。然后就可以直接套用Dijkstra算法了

A longest path between two given vertices s and t in a weighted graph G is the same thing as a shortest path in a graph −G derived from G by changing every weight to its negation.

这甚至可能是更简单的 Dijkstra 的特例...不确定。

要检索最长的路径，请从末尾开始并向后走：

从具有最大 DTA 的顶点开始 V_max
找到结束于 V_max (edge->dest = V_max)
找到 DTA 值比最大值 (DTA[Src_max] == DTA[V_max] - 1) 小 1 的边 Src_max
递归地重复这个直到没有更多的源顶点

为了提高效率，您可以在下降的过程中反转边缘的端点，然后沿着路径返回起点。这样每个反向步骤都是 O(1).

Answer 3

我认为选项 3 最有希望。您可以使用 DSF 从所有根顶点（没有传入边的顶点）开始搜索最长路径，并为遇到的每个顶点增加 'max distance'。

这是一个非常简单的解决方案，但它可能会多次遍历某些路径。例如，对于边 (a,f)、(b,c)、(c,f)、(d,e)、(e,c)

a------------f
            /
   b----c--/
       /
d--e--/

（全部向右）起始顶点为a、b、d，边(c,f)会被遍历两次，顶点f的距离会被更新三次。如果我们在一个简单的链中将字母表的其余部分附加到 f，

a------------f-----g--  -  -  ---y---z 
            /
   b----c--/
       /
d--e--/

从 f 到 z 的整条链也可能被遍历 3 次。

您可以通过分离阶段并修改它们之间的图形来避免这种情况：在找到所有起始顶点 (a, b, d) 后，增加每个可用顶点与 (f, c, e) 的距离，然后从图中删除起始顶点及其边 - 只要保留一些边就重新迭代。
这将在第一步之后转换示例图，如下所示：

             f-----g--  -  -  ---y---z 
            /
        c--/
       /
   e--/

我们可以看到所有的交汇点（c 和 f）都将等待，直到找到最长的路径 到它们 ，然后再让分析进一步经过它们。

这需要迭代寻找起始顶点，这可能很耗时，除非您进行一些预处理（例如，计算每个顶点的所有传入边并将顶点存储在某种排序数据结构中，如整数索引多图或一个简单的最小堆。）

问题仍然悬而未决，与多次遍历特定图中公共路径的某些最终部分相比，截断图并重新扫描它以获取新根顶点的全部开销是否产生净收益...

给定一个 DAG，最长路径的长度和它结束的节点，我如何追溯我的步骤以便打印最长路径的每个节点？

Given a DAG, the length of the longest path and the node in which it ends, how do I retrace my steps so I can print each node of the longest path?

c

algorithm

graph-theory