制作Dijkstra算法账户回程时间

Question

这样的问题去如下：未加权树提供给我，让我可以在任一节点，即时通讯预计参观的是香港专业教育学院在阵列中提供了只有特定的节点启动。我的目标是找出需要花费的时间来到每个节点。每条边都需要一分钟才能通过。

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

这个问题的一个例子在上图中。假设我希望访问节点[90,50,20,75]，我开始在节点90并遍历到节点50，然后到达节点20，我将如何使Dijkstra的算法考虑在到达节点20之前返回到节点50的返回行程时间？

Answer 1

让我阐述我的意见：首先，我们将在树修复任意根，使得树植根（也许你已经有一个根树）。然后，第一步是找到一个最小长度周期，该周期从根开始并结束于根，并通过所有期望的节点。

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

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

为了确定最优性，还有一步是必需的。但让我告诉你到现在为止的代码。我已经在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) { 
 
\t var subPath = []; 
 
\t var currentNodeIncluded = false; 
 
\t if(nodesToVisit.indexOf(treeNode.value) != -1) { 
 
\t \t //this node should be visited 
 
\t \t subPath.push({node: treeNode, passThrough: false}); 
 
\t \t currentNodeIncluded = true; 
 
\t } 
 
\t 
 
\t //find the subpath for all subtrees 
 
\t if(treeNode.children) { 
 
\t \t for(var i = 0; i < treeNode.children.length; ++i) { 
 
\t \t \t var subTreePath = findCycle(treeNode.children[i], nodesToVisit); 
 
\t \t \t if(subTreePath.length > 0) { 
 
\t \t \t \t if(!currentNodeIncluded) { 
 
\t \t \t \t \t subPath.push({node: treeNode, passThrough: true}); 
 
\t \t \t \t \t currentNodeIncluded = true; 
 
\t \t \t \t } \t \t \t 
 
\t \t \t \t //if we need to visit this subtree, merge it to the current path 
 
\t \t \t \t subPath = subPath.concat(subTreePath); 
 
\t \t \t \t subPath.push({node: treeNode, passThrough: true}); //go back to the current node 
 
\t \t \t } 
 
\t \t } 
 
\t } 
 
\t 
 
\t return subPath; 
 
} 
 

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

 
function printPath(path) { \t 
 
\t for(var i = 0; i < path.length; ++i) 
 
\t \t if(path[i].passThrough) 
 
\t \t \t console.log("Pass through " + path[i].node.value); 
 
\t \t else 
 
\t \t \t 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 

现在最重要的是找到最佳解决方案，最终切割的路径段实际上是最长的路径段。在上面的代码中，情况并非一定如此，因为您可以自由选择处理子树的顺序，并且如果您位于应该访问的节点，则可以自由地进行实际访问（与传递对比）访问子树之间的任何地方。

为了做到这一点，发现所有需要的节点（其可以高效率地对树进行）之间的距离。距离最远的一对将是开始和结束节点。因此，您需要确保他们在循环中的访问随后发生（即在他们之间没有其他节点访问过）。您可以通过在递归调用返回的路径段的开始和结束处强制执行特定的访问节点来执行此操作。例如，如果子路径包含开始或结束节点，则也会返回递归调用。在调用函数中，将这些子路径按正确的顺序排列。这也将简化removeLongestPassThroughSegment()函数，因为您已经知道最长的路径贯穿段。