使Dijkstra的算法考虑回程旅行时间

Question

所以问题如下：向我提供了一个未加权的树，并允许我从任何节点开始，我预计只访问数组中提供的某些节点。我的目标是找到前往每个所需节点所需的时间量。每个边缘都需要一分钟的时间。

这个问题的一个例子在上图中。假设我希望访问节点[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) {
	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);