两个节点碰撞所需的时间

Question

给定一个由 N 个节点组成的图，节点编号为 (1-N)，每个节点都恰好有一条指向某个节点的有向边（可以是指向自身）。

我们需要回答以下类型的查询：A, B，询问两个物体在碰撞时所需的时间，其中一个从 A 开始移动，另一个从 B 开始移动。两个物体每次移动 1 个节点，每次移动花费 1 秒。如果它们无法相遇，则返回时间为 -1。

时间：从 X 到 Y：每经过 1 个节点需要 1 秒。 限制条件：

N, Q <= 10^5 (number of nodes, number of queries).

例子：给定一个图形

   A -> B -> C -> D -> E
                  ^    |
                  K <- F

Query(A, E) : 3 seconds, as at time t = 3 secs they both will be on node D.
Query(C, D) : -1 seconds, as they will never collide.

什么是最佳的回答查询的方式？

暴力方法：时间 - O(Q * N)

使用二进制抬升技术的改进解决方案：时间 - O(Q * log(N))

private static int[] collisionTime(int N, int Q, int[] A, int[][] queries) {

    // ancestor matrix : creation time- O(n * log(n))
    int M = (int) (Math.ceil(Math.log10(N) / Math.log10(2))) + 1;
    int[][] ancestor = new int[N + 1][M];
    for(int i = 1; i <= N; i++) {
        ancestor[i][0] = A[i]; // 2^0-th ancestor. 
    }
    for(int j = 1; j < M; j++) {
        for(int i = 1; i <= N; i++) {
            ancestor[i][j] = ancestor[ancestor[i][j-1]][j-1];
        }
    }

    int[] answer = new int[Q];
    for(int i = 0; i < Q; i++) { 
        int u = queries[i][0];
        int v = queries[i][1];
        answer[i] = timeToCollide(u, v, ancestor);
    }

    return answer;
}

// using binary lifting: time- O(log(n))
private static int timeToCollide(int u, int v, int[][] ancestor) {
    int m = ancestor[0].length;

    // edge cases
    if(u == v)                              // already in collision state
        return 0;              
    if(ancestor[u][m-1] != ancestor[v][m-1]) // their top most ancestor is not the same means they cannot collide at all.
        return -1;

    int t = 0;
    for(int j = m - 1; j >=0; j--) {
        if(ancestor[u][j] != ancestor[v][j]) {
            u = ancestor[u][j];
            v = ancestor[v][j];
            t += Math.pow(2, j);
        }
    }
    return t + 1;
}

- tusharRawat

---

从图中，您可能会得到循环和“队列”大小，因此可以使用模数。无需暴力破解。 - Jarod42

@AKSingh 这将使总时间为 O(N^2 + Q)，这与 O(Q*N) 没有实质性的改进。 - RBarryYoung

@tusharRawat 是的，这就是我一直在想的。我认为构建它需要O(N log N)的时间，然后回答查询需要O(Q log N)的时间。因此总时间复杂度为O((N+Q) log N)。 - RBarryYoung

@AKSingh，我将使用二进制提升来添加我的解决方案。问题现在不可用，所以您现在无法访问它，但是如果您需要，我可以提供4-5个样例测试案例。 - tusharRawat

事实上，我相当确定我可以获得O(N + Q)的平均时间复杂度。对于任意随机结构或随机查询集，它几乎总能达到这个复杂度。然而，对于某些病态结构和非随机查询集（始终匹配，但距离最大），我还没有完全解决。 - RBarryYoung

Answer 1

1. 查找所有终端循环，并指定每个终端循环中的任意一个顶点作为循环根（O（N））
2. 对于每个顶点，记录其终端循环的长度，进入终端循环的距离和到终端循环根的距离（O（N））。
3. 断开每个循环根的出站链接。这将图形转换为森林。
4. 对于每个查询，在此森林中找到两个查询节点的最近（最低）公共祖先。
5. 从保存有关每个查询节点和最低共同祖先的信息中，您可以在恒定时间内计算出发生碰撞的时间。

第4步，即最低公共祖先查询，是一个非常研究充分的问题。最好的算法仅需要线性处理时间并提供恒定的查询时间，从而导致此问题总体的O（N + Q）时间。

- Matt Timmermans

---

我一直在准备一个与此非常相似的答案。然而，通过切断循环根节点的出链（步骤3），您实际上改变了一些查询答案。我认为这仍然可以工作，因为当我分类所有可能发生碰撞的方式时，任何在循环中发生的碰撞都可以在有效的O(1)时间内确定。 - RBarryYoung

是的。这就是为什么除了距离到循环根之外，您还需要距离到循环和循环长度的原因。 - Matt Timmermans

我一直在阅读维基百科关于LCA和相关的重路径分解文章，但似乎它们没有足够的信息来实现任何O(n)算法。他们还暗示其中一些算法“更难实现”，这似乎很不祥。你有什么建议可以实现描述呢？ - RBarryYoung

@RBarryYoung 由于您不必按给定顺序处理查询，因此可以使用Tarjan的LCA算法，该算法简单快速：https://en.wikipedia.org/wiki/Tarjan%27s_off-line_lowest_common_ancestors_algorithm 对于中序处理，我会使用通过Euler遍历描述的范围最小查询的缩减：http://www-di.inf.puc-rio.br/~laber/lca-rmq.pdf 那个需要很多代码。 - Matt Timmermans

哦，我错过了LCA文章中的那个链接（可能是因为我没有理解在线/离线的含义）。我会去看一下...谢谢你提供的链接。 - RBarryYoung

Answer 2

我认为以下方法在技术上实现了O(N+Q)的时间复杂度。

观察

子图:图形不一定是连续的。所有图形都包含一个或多个不相交的完整连续子图，意味着：

• 没有节点在子图之间共享("不相交")
• 子图中的所有节点都连接在一起("连续")
• 没有路径连接不同的子图("完整")

我将在此后称这些图形为图的子图或只是"子图"。这些子图具有以下附加属性，这些属性是它们的定义（上面）和图形中的节点类型（它们都是具有一个外向边/指针的"父指针节点"）的结果:

• 所有这样的子图必须有一个循环（因为循环是它们终止或关闭的唯一方式）
• 循环可以是任意长度cycle.Len >= 1
• 此外，可能有任意数量的树(t >= 0)附加到其根（底部）的循环上
• 所有节点都在循环中或在这些树之一中（树的根位于循环中，但也计算为树的一部分）

术语:

• 循环长度:循环中节点的数量。
• 循环基准:在循环中选择的任意节点，用于测量两个节点之间的距离，无论这两个节点是在同一个循环中还是在同一个子图中。
• 树基准:附加到循环上的树的基础节点或根节点。由于树基准也是将其连接到循环的节点，因此树基准节点被计算为在循环中（并且也是其树的一部分）。
• 距离:对于循环中的节点，这是从该节点到循环基准的距离(跳数)（如果它是循环基准则为0）。对于树中的节点（不包括树基准节点，树基准节点算作在循环中），这是从该节点到树基准节点的距离。

碰撞情况

微不足道

在图中可能有许多种碰撞方式或"形式"，但我们可以预先识别出两种微不足道的情况：

(A, B) 关系	是否碰撞？	碰撞距离
相同节点	是	0
不同的子图	否	-1

显然，如果A和B是同一个节点，则它们相撞的距离为零。同样，如果它们位于两个不同的子图中，则它们永远不会相撞，因为子图之间没有连接。对于接下来的碰撞情况，我将假定这两种情况已经被过滤，以便：

1. A和B被认为是不同的节点，且 2. A和B被认为在同一个子图中

非平凡关系：

下表涵盖了两个节点之间所有其他的、非平凡的关系。

(A, B) 关系 | 是否相撞？ | 碰撞距离 | 备注 -|-|-|- 在同一圈中 | 否 | -1 | 圈中的节点始终保持相同的距离 A在树中，B在环中（或反之） | 如果它们同时到达A的treeBase | -1 或者 A.treeDist | 如果 B.cycleDist = (A.treeDist MOD cycle.Len) A和B在不同的树中 | 如果A和B到其cycle.Base的距离等于MOD cycle.Len | MAX(A.treeDist, B.treeDist) | 当更远的节点到达环（树根）时，它们相遇 A和B在同一棵树中，但有不同的treeDist | 如果它们的treeDist取模后相等 | MAX(A.treeDist, B.treeDist) | 当更远的节点到达环（树根/基）时，它们相遇 A和B在同一颗树上，并且treeDist相等 | 是 | 在它们在树中的最低共同祖先（LCA）处 | 必须向树上查询

以上几次应用了一个重要原则，即圈中两个不同的节点永远不会相撞。这是因为当每个节点沿着其路径绕着圈走时，它们总是保持相同的距离，没有一种方法可以让一个节点的路径在圈中"追上"另一个节点的路径。只有如果它们从圈中的同一个节点开始，它们才能相撞。

这意味着：

1. 一个环中的两个不同节点永远不会相撞。
2. 一棵树中的节点只能与一个在环中的节点相撞，如果它们到环基点的距离之和对于循环长度取模后相同(也就是除以循环长度的余数相同）。
3. 对于两个不同树的节点和同一棵树但距离树基点不同的两个节点，这也是正确的。
4. 在所有这些情况（来自#2和#3）中，当最远离其树基点的节点到达循环时（也是其树基点），它们将相撞。 这是因为环中的节点无法“追赶”对方，因此一旦它们同时进入环中，它们必须始终保持相同。 因此，当更远的节点最终到达循环基点时，它们总是会相撞。

另一个重要的结果是，表格中所有情况都可以用O（1）时间回答，除了最后一个，只需用以下简单确定的信息注释节点即可：

1. 它们的基础节点（树或循环）
2. 它们到该基础节点的距离
3. 它们所属的子图
4. 它们所在子图的循环长度

当初始化图时，这些都可以在每个节点O(1)或总时间O（N）内轻松确定。

方法

节点

在节点最初加载到图中(MPDGraph对象)后，我用上面列出的其他信息注释节点。该过程（称为代码中的“映射”）如下进行：

1. 选择任何一个节点
2. 沿着它的路径一直走，直到到达了已经在它的路径上的节点或已经被映射过的节点
3. 如果#2穿过了自己的路径，则我们找到了一个新的循环。将我们穿过的节点指定为循环的基点，并填充映射属性(cycle, 基点节点, 距离等）。逐步解开我们的路径，每次向上返回并标记其为InCycle，直到我们再次到达基本节点。此时，我们位于我们的路径进入环形的树的底部，因此当我们返回路径中的上一个节点时，我们将转而将其标记为树节点，直到返回我们路径中的第一个节点。
4. 如果相反，＃2达到了已映射的节点，则我们将把路径附加到该节点并复制其树/循环、基点等信息到我们当前的节点。然后，像#3一样返回我们的路径，设置每个节点的映射属性。
5. 如果有任何未映射的节点，请选择一个并转到＃2。

这需要O（N）时间。

查询

我们有一个方法（称为MPDGraph.FindCollision），给定两个节点，将应用上面的两个碰撞案例表中的规则并返回结果。 对于除最后一个情况（在同一树上且距离相同的节点）之外的每种情况，都可以通过使用映射属性在O(1)时间内确定距离。

如果两个节点在同一颗树中，且距离基准节点相同，则它们可以在它们之间和共同的treeBase节点之间的任何地方相遇。 对于这种情况，FindCollision(A,B)方法调用findTreeDistance(A,B)方法：

1. 如果它们是同一节点，则返回零。 2. 否则，它会检查以前计算过的距离的高速缓存，查看是否已经为这两个节点计算了距离。 如果是，则返回该值。 3. 否则，它调用findTreeDistance，传入当前两个节点的父节点以获取它们之间的距离，并加上1。 然后将其添加到缓存中并返回该值。

没有这种记忆化（即缓存），每次查询此类型平均需要约O(log N)。 带有缓存时很难计算，但我猜不会更差于O(log log N)，但对于Q远大于N的情况，这将收敛到O(1)。

这使得查询处理时间复杂度在O(Q log log N)和O(Q)之间，总时间在O(N + Q(log log N))和O(N + Q)之间。

代码

public static int[] collisionTime(int N, int Q, int[] A, int[,] queries)
{
    // create the graph and fill-in the mapping attributes for all nodes
    var graph = new MPDGraph(A);
    graph.MapAllNodes();

    int[] answers = new int[queries.GetLength(0)];
    for (int i = 0; i < answers.Length; i++)
    {
        answers[i] = graph.FindCollision(queries[i, 0], queries[i, 1]);
    }

    return answers;
}

这里使用了以下类：

MPDGraph 类:

// MPDG: Mono-Pointing, Directed Graph 
//  An MPDG is a directed graph where every node has exactly one out-edge.
//  (MPDG is my own term, I don't know the real name for these)
class MPDGraph
{
    public Node[] Nodes;
    Dictionary<(Node, Node), int> cachedDistances = new Dictionary<(Node, Node), int>();

    // constructor
    public MPDGraph(int[] Pointers)
    {
        Nodes = new Node[Pointers.Length];

        // first fill the array with objects
        for (int i = 0; i < Nodes.Length; i++) { Nodes[i] = new Node(i); }

        // apply their pointers
        for(int i = 0; i < Nodes.Length; i++) { Nodes[i].toNode = Nodes[Pointers[i]]; }
    }


    // map all of the nodes by filling their mapping properties
    public void MapAllNodes()
    {
        for(int i=0; i<Nodes.Length; i++)
        {
            if (!Nodes[i].isMapped)
                MapPath(Nodes[i], 1);
        }
    }

    // recursively map a path of unmapped nodes, starting from curr
    //  returns true if curr is in a cycle, false otherwise
    public Boolean MapPath(Node curr, int pathNo)
    {
        Boolean inCycle = false;
        curr.pathNo = pathNo;

        Node next = curr.toNode;

        if (next.IsInPath)
        {
            // we have found a new cycle
            Cycle Cycle = new Cycle(this, next, curr.pathNo - next.pathNo + 1);
            curr.Map(Cycle);
            return true;
        }
        else if (next.isMapped)
        {
            // we are joining an already partially mapped tree
            if (next.IsInCycle)
            {
                // next is a tree-Base, the top of our tree and also in the cycle
                curr.Map(next.Cycle, false, next, 1);
            }
            else
            {
                // next is a normal tree-node
                curr.Map(next.Cycle, false, next.BaseNode, next.Distance + 1);
            }
            return false;
        }
        else
        {
            // continue forward on the path, recurse to the next node
            inCycle = MapPath(next, pathNo+1);

            if (inCycle)
            {
                if (next.Cycle.Base == next || next.Distance == 0)
                {
                    //we have returned from the cycleBase, which is also a treeBase
                    // so, switch from Cycle to Tree
                    curr.Map(next.Cycle, false, next, 1);
                    return false;
                }
                else
                {
                    // still in the cycle
                    curr.Map(next.Cycle);
                }
            }
            else
            {
                //returned in tree
                curr.Map(next.Cycle, false, next.BaseNode, next.Distance + 1);
            }

            return inCycle;
        }

    }


    // Given two starting nodes, determine how many steps it takes until their
    //  paths collide. Returns -1 if they will never collide.
    public int FindCollision(int index1, int index2)
    {
        Node node1 = Nodes[index1];
        Node node2 = Nodes[index2];

        // eliminate trivial cases
        if (node1.Cycle != node2.Cycle)
            return -1;      // cant collide if they're in different subgraphs
        else if (node1 == node2)
            return 0;       // if they're the same node, then distance = 0
        else if (node1.IsInCycle && node2.IsInCycle)
            return -1;      // different nodes in a cycle never collide
        
        else
        {  // they're both in the same subgraph, use math to tell if they collide

            // get their distances to the cycle base
            int dist1 = node1.Distance + (node1.IsInCycle ? 0 : node1.BaseNode.Distance);
            int dist2 = node2.Distance + (node2.IsInCycle ? 0 : node2.BaseNode.Distance);
            int cycleLen = node1.Cycle.Length;

            // use math:  modulo(cycle length)
            if ((dist1 % cycleLen) != (dist2 % cycleLen))
            {
                return -1;      // incompatible distances: cannot possibly collide
            }
            else
            {
                // they must collide somewhere, figure out how far that is
                if (node1.IsInCycle || node2.IsInCycle)
                {
                    // if one is in the cycle, they will collide when
                    // the other one reaches the cycle (it's treeBase)
                    return (!node1.IsInCycle ? node1.Distance : node2.Distance);
                }
                else if (node1.BaseNode != node2.BaseNode)
                {
                    // They are in different trees:  they will collide at
                    //  the treeBase of the node that is farther
                    return Math.Max(node1.Distance, node2.Distance);
                }
                else
                {
                    // They are in the same tree:
                    if (node1.Distance != node2.Distance)
                    {
                        //if they are in the same tree, but have different distances
                        //  to the treeBase, then they will collide at the treeBase
                        //  when the farther one arrives at the treeBase
                        return Math.Max(node1.Distance, node2.Distance);
                    }
                    else
                    {
                        //  the hard case, have to walk down their paths
                        //  to find their LCA (Lowest Common Ancestor)
                        return findTreeDistance(node1, node2);
                    }
                }
            }
        }
    }


    int findTreeDistance(Node node1, Node node2)
    {
        if (node1 == node2) return 0;

        // normalize their order
        if (node1.index > node2.index)
        {
            var tmp = node1;
            node1 = node2;
            node2 = tmp;
        }

        // check the cache
        int dist;
        if (cachedDistances.ContainsKey((node1,node2)))
        {
            dist = cachedDistances[(node1, node2)];
        }
        else
        {
            // keep recursing to find where they meet
            dist = findTreeDistance(node1.toNode, node2.toNode) + 1;
            // cache this new distance
            cachedDistances.Add((node1, node2), dist);
        }
        return dist;
    }
}

节点类：

// Represents a node in the MPDG (Mono-Pointing Directed Graph) with the constraint
//  that all nodes have exactly one out-edge ("toNode").
class Node
{
    // Primary properties (from input)
    public int index { get; set; }      // this node's unique index (to the original array)
    public Node toNode { get; set; }    // what our single out-edge is pointing to


    public Node(int Index_) { this.index = Index_; }


    // Mapping properties
    // (these must be filled-in to finish mapping the node)

    //  The unique cycle of this node's subgraph (all MPDG-subgraphs have exactly one)
    public Cycle Cycle;

    //  Every node is either in their subgraphs cycle or in one of the inverted
    // trees whose apex (base) is attached to it.  Only valid when BaseNode is set.
    // (tree base nodes are counted as being in the cycle)
    public Boolean IsInCycle = false;

    // The base node of the tree or cycle that this node is in.
    //  If (IsInCycle) then it points to this cycle's base node (cycleBase)
    //  Else it points to base node of this node's tree (treeBase)
    public Node BaseNode;

    //  The distance (hops) from this node to the BaseNode
    public int Distance = -1;    // -1 if not yet mapped

    // Total distance from this node to the cycleBase
    public int TotalDistance { get { return Distance + (IsInCycle ? 0 : BaseNode.Distance); } }


    // housekeeping for mapping nodes
    public int pathNo = -1;          // order in our working path

    // Derived (implicit) properties
    public Boolean isMapped { get { return Cycle != null; } }
    public Boolean IsInPath { get { return (pathNo >= 0); } }


    public void Map(Cycle Cycle, bool InCycle = true, Node BaseNode = null, int distance_ = -1)
    {
        this.Cycle = Cycle; 
        IsInCycle = InCycle;

        if (InCycle)
        {
            this.BaseNode = Cycle.Base;
            Distance = (Cycle.Length + (Cycle.Base.pathNo - pathNo)) % Cycle.Length;
        }
        else
        {
            this.BaseNode = BaseNode;
            Distance = distance_;
        }

        pathNo = -1;    // clean-up the path once we're done
    }
}

循环类：

// represents the cycle of a unique MPDG-subgraph
//  (should have one of these for each subgraph)
class Cycle
{
    public MPDGraph Graph; // the MPDG that contains this cycle
    public Node Base;      // the base node of a subgraph's cycle
    public int Length;     // the length of this cycle

    public Cycle(MPDGraph graph_, Node base_, int length_)
    {
        Graph = graph_;
        Base = base_;
        Length = length_;
    }
}

性能测量：

节点数	构建和映射图表 平均微秒数	问题数量	所有问题 平均微秒数	问题的平均 微秒数	总平均 微秒数
50	0.9	1225	26	0.0212	26.9
500	10.1	124750	2267	0.0182	2277.1
1000	23.4	499500	8720	0.0175	8743.4
5000	159.6	12497500	229000	0.0183	229159.6
10000	345.3	49995000	793212	0.0159	793557.3

- RBarryYoung

---

我认为找到一个O(QN)的情况并不太难——两条长路径到达合并点，然后是通向终端循环的路径。查询第一条长路径的初始节点与第二条长路径的每个节点。每次检查距离缓存都会有一个唯一的键。如果您想要O(N+Q)，则需要使用良好的LCA算法。 - Matt Timmermans

我已经在它上面尝试了几个病态案例，无论如何，随着Q的增大，它都接近于O(N+Q)。这就是为什么我说它技术上是O(N+Q)。虽然我同意，使用LCA算法会更好。 - RBarryYoung

从技术上讲，如果Q == N，那么O(N+Q)等同于O(N)，但是如果Q = N，则为O(N^2)，因为有这么多个不同的缓存键。 - Matt Timmermans

@MattTimmermans 你有相关的参考资料吗？因为在这种情况下，N和Q都是总体n的细分，在正式的O(n)定义中，即n = N + Q。我从未见过像这样的情况的大O形式描述。通常的奇怪情况是像O(m)或O(n+m)这样的东西，其中m是一个参数的数量级，而且你必须转换为比特复杂度（即n = log m），但不是像这样的情况。 - RBarryYoung

@MattTimmermans 好的，我一直在重新运行我的测试，对于N=Q的随机树和查询似乎表现出类似于O(n log log n)的东西。我可能会尝试使用二叉树作为我的算法的可能最坏情况。 - RBarryYoung

Answer 3

只有在具有多个链接的节点上才可能发生碰撞。例如您示例中的节点D。

让我们称这些节点为“碰撞站点”

因此，您可以将图形修剪为仅包含碰撞站点节点。导致碰撞站点节点的节点成为碰撞站点节点的属性。

就像您示例中的这样：

D : { A,B,C }, { E,F,K }

只有在起始节点位于同一碰撞站点节点的两个不同属性列表上时，才可能发生碰撞。

一旦确定可能发生碰撞，就可以检查两个起始节点是否与碰撞站点的距离相同。

算法：

Prune graph to crash site nodes
LOOP over questions
Get 2 start nodes
LOOP over crash sites
   IF start nodes on two different attributes of crash site
        IF start nodes are equi-distant from crash site
             report crash time
             BREAK from crash site loop

这是一个随机生成的图形，有50个节点，每个节点都有一条出边与另一个随机选择的节点相连。

碰撞位置为

5 7 8 9 10 11 18 19 23 25 31 33 36 37 39

因此，该算法最多只需要循环15个节点，而不是50个。

对于问题“两个特定节点是否相撞？”，答案几乎总是“否”。这样有点无聊。因此，让我们提出一个稍微不同的问题：“对于一个特定的图形，哪些节点对会导致碰撞？”这需要相同的算法（应用于每对节点），但总是产生有趣的答案。

对于这个图形

我得到了这个答案

0 and 29 collide at 41
1 and 5 collide at 40
2 and 23 collide at 13
8 and 16 collide at 34
8 and 22 collide at 34
8 and 39 collide at 34
9 and 30 collide at 37
10 and 31 collide at 25
11 and 47 collide at 23
12 and 28 collide at 25
12 and 35 collide at 25
12 and 49 collide at 25
13 and 38 collide at 27
14 and 44 collide at 1
15 and 17 collide at 0
15 and 18 collide at 0
15 and 37 collide at 0
16 and 22 collide at 34
16 and 39 collide at 34
17 and 18 collide at 0
17 and 37 collide at 0
18 and 37 collide at 0
20 and 26 collide at 9
20 and 42 collide at 9
20 and 43 collide at 9
21 and 45 collide at 24
22 and 39 collide at 34
25 and 34 collide at 3
26 and 42 collide at 9
26 and 43 collide at 9
28 and 35 collide at 25
28 and 49 collide at 25
32 and 48 collide at 34
33 and 36 collide at 7
35 and 49 collide at 25
42 and 43 collide at 9

一些时间结果

节点数	崩溃站点 毫秒	问题数量	问题平均值 微秒
50	0.4	1225	0.02
500	50	124750	0.02
5000	5500	~12M	0.02
10000	30000	~50M	0.03
30000	181000	~450M	0.6

注：

• 一个问题的平均时间是检查每对节点可能的碰撞的平均时间。
• 回答单个问题非常快，对于中等大小的图（<10,000个节点），大约为20纳秒[以前的计时报告包括在发现碰撞时输出结果，这比检测碰撞要花费更长时间。这些结果是在将所有输出到控制台的注释中进行的。]
• 设置崩溃现场及其支流会使中等大小的图（>5,000个节点）变慢。只有在需要问很多问题时才值得这样做。

此代码可在https://github.com/JamesBremner/PathFinder上获得。

- ravenspoint

---

所以，如果我正确地读取了您的时间结果，您的问题列表实际上包括了每个可能的不同问题，对吗？ - RBarryYoung

@RBarryYoung 是的。 - ravenspoint

OP的“二进制提升”技术在最坏情况下更快。 - Matt Timmermans

此外，如果崩溃位置在终端周期上，则即使两个节点的距离不同，只要差值是周期长度的倍数，它们也可能发生碰撞。 - Matt Timmermans

也许吧。但最坏情况非常罕见。所以问题是，你的例行程序有多快。我没有看到其他回答这个问题的方法的计时报告。 - ravenspoint