给定一个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，最长路径开始的顶点在其相邻列表中具有路径的最远节点。

我想到了三种解决方案，但没有一种看起来很棒。

>

迭代权重为0的每个顶点的边（因此没有前身），如果有选择，请避免选择将其与最远节点连接的边（如前所述，起始节点和结束节点之间的最短路径为1）

在跟踪拓扑排序数组中每个节点的最大距离的数组中：从表示我们找到的最远节点的索引开始，查看前一个节点是否具有兼容的距离（如中所示，前一节点的距离比最远节点少1）。如果是，请检查其邻接列表，以查看最远的节点是否在其中（因为如果最远节点的距离为10，则可能有多个距离为9但未连接到该节点的节点）。重复上述步骤，直到到达路径的根。

到目前为止最可能的候选，创建一个指针数组，跟踪每个节点的“最大”父节点。在上面的代码中，每当一个节点的最大距离改变时，意味着它的父节点(如果有的话)比前一个父节点的距离更长，这意味着我们可以改变与当前节点相关的最大父节点。

编辑:我最后只是分配了一个新的数组，每次我更新一个节点的权重(DTA[tmp-

Answer 1

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

这是一个非常简单的解决方案，但它可能会多次遍历某些路径。例如，对于边（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的整个链条可能也会被遍历三次。

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

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

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

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

问题仍然悬而未决，截断一个图并重新扫描它以寻找新的根顶点的整个开销是否与多次遍历特定图中公共路径的某些最终部分相比有净收益…

Answer 2

我想这解决了问题，除非有什么我不明白的。

如果将边缘权值设为负值，则DAG中的最高权值路径等效于最低权值路径。然后您可以直接应用Dijkstra算法。

加权图G中两个给定顶点s和t之间的最长路径与图中的最短路径相同−通过将每个权重改为负值，从G派生出G。

这甚至可能是Dijkstra的一个特例，更简单…不确定。

要检索最长的路径，请从末端开始，然后向后：

1. 从具有最大 DTA V_max的顶点开始
2. 查找以V_max结束的边缘（边缘-

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

Answer 3

我假设图的边缘是u。

我建议你转储拓扑排序。相反：

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

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