使 Dijkstra 算法考虑 return 旅行时间

Question

所以问题如下：向我提供了一个未加权的树，它允许我从任何节点开始，我希望只访问我在数组中提供的某些节点。我的目标是找出到达每个所需节点所需的时间。每条边都需要一分钟的时间。

我已经尝试实施 Dijkstra 算法，以便从我想访问的节点开始并尝试从那里形成最短路径。但我的问题是，虽然提供了解决方案，但它可能不是最有效的解决方案，因为我不知道如何强制 Dijkstra 算法考虑两次在同一边缘上的行进。

上图中就是这个问题的一个例子。假设我想访问节点 [90,50,20,75] 并且我从节点 90 开始并遍历到节点 50 然后到节点 20 我如何让 Dijkstra 的算法考虑 return 到节点 50 的旅行时间在到达节点 20 之前？

Answer 1

让我详细说明一下我的意见：首先，我们将在树中固定一个任意根，这样树就有根了（也许你已经有根树了）。然后，第一步是找到一个从根开始到根结束并通过所有所需节点的最小长度循环。

这可以通过分而治之的方法来完成。如果您在任何节点，您可以检查是否需要在路径中包含该节点。如果是这样，你会的。然后，对于每个子树，只需使用相同的方法并在必要时扩展路径。最后，确保子路径 returns 到当前子树的根（代码如下）。

找到循环后，您需要删除最长的子路径，以便最终得到非循环路径。这可以通过循环遍历在线性时间内完成。在我的实现中，我让循环提取不仅发出节点序列，还发出一个标志，用于确定路径是否只是通过一个节点（并且不访问该节点）。因此，这一步只是简单地找到实际访问过的任意两个节点之间的路径段。

为了断言最优性，还缺少必要的一步。但是，让我向您展示到目前为止的代码。我已经在 JavaScript 中实现了它，因为您可以运行它在 SO 上。实现的目标是可理解性而不是效率。

//the tree from your example
var tree = { value: 90, children: [{ value: 50, children: [{ value: 20, children: [{ value: 5 }, { value: 25 }] }, { value: 75, children: [{ value: 66 }, { value: 80 }] }] }, { value: 150, children: [{ value: 95, children: [{ value: 92 }, { value: 111 }] }, { value: 175, children: [{ value: 166 }, { value: 200 }] }] }] };

var nodesToVisit = [90, 50, 20, 75];
//var nodesToVisit = [92, 111, 166];

function findCycle(treeNode, nodesToVisit) {
 var subPath = [];
 var currentNodeIncluded = false;
 if(nodesToVisit.indexOf(treeNode.value) != -1) {
  //this node should be visited
  subPath.push({node: treeNode, passThrough: false});
  currentNodeIncluded = true;
 }
 
 //find the subpath for all subtrees
 if(treeNode.children) {
  for(var i = 0; i < treeNode.children.length; ++i) {
   var subTreePath = findCycle(treeNode.children[i], nodesToVisit);
   if(subTreePath.length > 0) {
    if(!currentNodeIncluded) {
     subPath.push({node: treeNode, passThrough: true});
     currentNodeIncluded = true;
    }   
    //if we need to visit this subtree, merge it to the current path
    subPath = subPath.concat(subTreePath);
    subPath.push({node: treeNode, passThrough: true}); //go back to the current node
   }
  }
 }
 
 return subPath;
}

function removeLongestPassThroughSegment(cycle) {
 var longestSegmentStart = -1;
 var longestSegmentEnd = -1;
 
 //the start of the current pass-through segment between non-pass-through nodes
 var currentStart = -1;
 var segmentLengthAtStart = -1;
 for(var i = 0; i < cycle.length; ++i) {
  if(!cycle[i].passThrough) {
   //we have found a node that we need to visit
   if(currentStart != -1) {
    var length = i - currentStart;
    if(length > longestSegmentEnd - longestSegmentStart) {
     longestSegmentStart = currentStart;
     longestSegmentEnd = i;
    }
   } else
    segmentLengthAtStart = i;
   currentStart = i;
  }
 }
 
 //check the path segment that wraps around
 if(cycle.length - currentStart + segmentLengthAtStart > longestSegmentEnd - longestSegmentStart) {
  longestSegmentStart = currentStart;
  longestSegmentEnd = segmentLengthAtStart;
 }
 
 //build the final path by cutting the longest segment
 var path = [];
 var i = longestSegmentEnd;
 do {
  path.push(cycle[i]);
  i++;
  if(i >= cycle.length)
   i = 0;
 } while(i != longestSegmentStart);
 path.push(cycle[longestSegmentStart]);
 return path;
}

function printPath(path) { 
 for(var i = 0; i < path.length; ++i)
  if(path[i].passThrough)
   console.log("Pass through " + path[i].node.value);
  else
   console.log("Visit " + path[i].node.value);
}

var cycle = findCycle(tree, nodesToVisit);
console.log("Cycle:");
printPath(cycle);

var path = removeLongestPassThroughSegment(cycle);
console.log("Final Path:");
printPath(path);

你会发现这段代码已经找到最优解并打印：

Final Path:
Visit 90
Visit 50
Visit 20
Pass through 50
Visit 75

即使对于一组更具挑战性的所需节点，这也会达到最佳路径 (var nodesToVisit = [92, 111, 166];)：

Final Path:
Visit 92
Path through 95
Visit 111
Pass through 95
Pass through 150
Pass through 175
Visit 166

现在找到最优解的本质是，最后切出的路径段实际上是最长的可能路径段。在上面的代码中不一定是这种情况，因为你可以自由选择处理子树的顺序，如果你在应该访问的节点上，你可以自由地放置实际访问（与传递相反) 访问的子树之间的任何位置。

为此，找到所有所需节点之间的距离（这可以在树上有效地完成）。距离最大的一对将是起始节点和结束节点。因此，您需要确保它们在循环中的访问随后发生（即它们之间没有访问其他节点）。您可以通过在递归调用 returned 的路径段的开头和结尾强制执行特定的访问节点来做到这一点。例如，如果子路径包含开始或结束节点，则让递归调用也 return。并在调用函数中，以正确的顺序放置这些子路径。这也将简化 removeLongestPassThroughSegment() 函数，因为您已经知道最长的路径段是什么。

使 Dijkstra 算法考虑 return 旅行时间

Making Dijkstra's algorithm account for return travel time

algorithm

tree

dijkstra