图中最短的部分路径

Question

我有一个由矩阵定义的网络，其中矩阵中的[i，j]元素是从节点i到节点j的成本。如果我和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] [i1，j1]，j> i和i1 > = j的。

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

Answer 1

你基本上有一个Directed Acyclic Graph (DAG)这里，你正在寻找它最长路径，根据w(u,v) - 在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-Complete。幸运的是，你的问题是一个DAG，并且它有一个高效的解决方案。首先topologically sort节点，然后 - 从后到前：

​​

当你完成后，对每个节点v d（五）将表示与此节点开始的最长路径，你只需要找到从这些中获得所需节点和最大值的最大值。

您可以通过以后重建的路径：

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