javascript - 如何获得比节点间最短路径更多的路径？

Question

在 d3.js 中，我使用名为 path 的函数来获取 2 个节点之间的最短路径。API 是这样说的:

node.path(target) <>

Returns the shortest path through the hierarchy from this node to the specified target node. The path starts at this node, ascends to the least common ancestor of this node and the target node, and then descends to the target node.

通过这个定义，我创建了一个新数组来保存两个节点之间的数据。我可以单击名为 beginNode 的第一个节点和名为 d 的第二个节点。它工作得很好，它们之间的最短路径保存在数组 shortest_path 中:

 .on("click", function(d, i) //Hier beginnt große "click"-Funktion
              {
shortest_path = beginNode && beginNode.path(d) || [];.....

有时有很多方法可以获取两个节点之间的路径，不仅是最短路径，还有更长的路径。现在，我的目标是将 2 个单击的节点之间的更多路径存储到该数组或另一个数组中。但不幸的是，d3,js 只提供最短路径功能。我希望你们中的一些人能够提供帮助。 Djikstra 是解决这个问题的正确方法吗？谢谢

Answer 1

这称为 k shortest paths problem 。您可以使用 Dijkstra 算法的变体 Eppstein's Algorithm 来解决这个问题。