图中的最短部分路径

Question

我有一个由矩阵定义的网络，矩阵中的i，j元素是从节点i到节点j的成本，如果i和j之间没有路径，那么i，j是无限的。

我用负值填充矩阵，所以如果i和j之间的距离很短，那么我在i，j中放入非常小的值，例如-50，如果距离很长，我放入更大的值，例如-5。

我想知道如何在网络中找到部分最短路径，唯一的约束是路径应该按预定义的顺序走，就像元素出现在矩阵i，i+1，i+2，…中一样。

对于简化的示例，

╔═══╦═══╦═════╦═══╦═══╦═════╗
║   ║ 1 ║  2  ║ 3 ║ 4 ║  5  ║
╠═══╬═══╬═════╬═══╬═══╬═════╣
║ 1 ║ 0 ║ -20 ║   ║   ║ -10 ║
║ 2 ║   ║   0 ║   ║   ║     ║
║ 3 ║   ║     ║ 0 ║   ║     ║
║ 4 ║   ║     ║   ║ 0 ║ -50 ║
║ 5 ║   ║     ║   ║   ║     ║
╚═══╩═══╩═════╩═══╩═══╩═════╝

在这里，完整的路径形式1到5等于-10，但是如果我们采用1到2的路径，然后是4到5，我们得到更好的分数-50，所以这里我们跳过3，对于部分路径是可以的。

因此，部分路径-是一条不需要访问每个节点的路径，它可能只是1到2的短段，但最短的部分路径必须是所有部分路径中最短的。

关于顺序的约束非常简单，我们总是从节点1开始搜索路径，并以升序进行，因此对于路径中的所有段i，j，j>i和i1>=j。

我想知道在网络中是否有找到最佳分数部分路径的好方法，我认为穷举搜索也是很好的解决方案，节点数量在15-20个左右。

Answer 1

根据w(u,v)，你基本上有一个Directed Acyclic Graph (DAG)，你正在寻找其中最长的路径-其中w(u,v)是每个连接(边)的正权重。如果u到v之间没有边，我们就用负无穷大来表示它的权重：w(u,v)=-infinity。

该图是G=(V,E)，其中V是包含所有节点的集合，E = { (u,v,w(u,v) | u<v}是边集合。

一般来说，Longest Path Problem是NP-完全的。幸运的是，您的问题是DAG，并且有一个有效的Dynamic Programming解决方案。首先topologically sort节点，然后-从最后到第一：

d(v) = max { d(u) + w(v,u) | for all edges (v,u) }

完成后，对于每个节点，v d(v)将表示从该节点开始的最长路径，您只需找到其中的最大值即可获得所需的节点和最大值。

您可以稍后通过以下方式重建路径：

v <- startNode //the node just found to be starting the desired path
list <- [v]
while (d(v) != 0):
   for each edge (v,u):
        if d(v) - w(v,u) == d(u):
             list.append(u)
             break
return list