标签: graph-theory

我不需要任何代码。只需向我解释一下问题（尤其是路径矩阵）。问题如下：

你和你获救的兔子囚犯需要逃离这个空间站倒塌的死亡陷阱——而且要快！不幸的是，有些兔子因长期监禁而变得虚弱，跑不了快。他们的朋友正在试图帮助他们，但如果你也参与进来，这次逃跑会更快。防御舱壁的门已经开始关闭，如果你不及时通过，你就会被困住！你需要抓住尽可能多的兔子，并在舱壁关闭之前穿过它们。

从起点移动到所有兔子和舱壁所需的时间将以整数方阵的形式给出。每行都会告诉您按顺序到达起点、第一只兔子、第二只兔子、……、最后一只兔子和舱壁所需的时间。行的顺序遵循相同的模式（开始、每个兔子、舱壁）。兔子可以跳进你的怀里，所以把它们捡起来是瞬间的，在舱壁密封的同时到达舱壁仍然可以让你成功逃脱，尽管是戏剧性的。（别担心，任何你没有捡到的兔子都可以和你一起逃走，因为它们不再需要携带你捡到的兔子。）如果你愿意，你可以重新访问不同的地点，并移动到舱壁并不意味着你必须立即离开——如果时间允许，你可以在舱壁之间来回走动去捡更多的兔子。

除了花时间在兔子之间旅行之外，一些路径还与空间站的安全检查站互动，并将时间倒回时钟。向时钟添加时间将延迟舱壁门的关闭，如果门已经关闭后时间回到 0 或正数，则会触发舱壁重新打开。因此，绕圈行走并不断获得时间是可能的：也就是说，每次经过一条路径，都会使用或增加相同的时间。

编写一个答案（times，time_limit）形式的函数来计算你可以捡起的兔子数量以及它们是哪些兔子，同时仍然可以在门永远关闭之前通过舱壁逃走。如果有多组相同大小的兔子，则按排序顺序返回囚犯 ID（作为索引）最低的兔子组。兔子按照囚犯 ID 排序，第一个兔子为 0。最多有 5 个兔子，time_limit 是一个非负整数，最多为 999。

例如，在以下情况

[
  [0, 2, 2, 2, -1],  # 0 = Start
  [9, 0, 2, 2, -1],  # 1 = Bunny 0
  [9, 3, 0, 2, -1],  # 2 = Bunny 1
  [9, 3, 2, 0, -1],  # 3 = Bunny 2
  [9, 3, 2, 2,  0],  # 4 = Bulkhead
]

时间限制为 1，内部数组的 5 行分别指定起点、兔子 0、兔子 1、兔子 2 和舱壁门出口。你可以采取以下路径：

Start End Delta Time …

我的 Java 应用程序中有一个图形遍历，在遍历完成后需要 300 毫秒以上才能填充路径对象。这很奇怪，因为它只发生在某些特定的遍历上，而其他遍历会立即填充它们的路径。这是 Java 代码示例，使用 Tinkerpop 3.3.1

我有一种情况，两个顶点由一条边直接连接。每次执行这个短遍历时，我都会得到很高的处理时间。如果我不执行 fill() 操作，遍历会立即完成。我还有其他需要遍历 10 多个边的遍历，并且它们在 < 1 毫秒内处理和填充路径。

在下面的代码中，我试图找到从“origs”中的顶点到“dests”中的顶点的最短路径，而不经过集合“avoids”中的任何顶点。遍历本身在 1 毫秒内完成，它的 fill() 方法消耗了时钟。

    Date startTime = new Date ();
    if (! dests.isEmpty ()){
        g.V (origs).where (is (P.without (avoids))).    
        repeat (
                out ().
                simplePath ().
                where (is (P.without (avoids)))
                ).
                until (is (P.within (dests))).
                limit (1).
                path ().
                fill (paths);  // This 'fill' is the line that can take > 300ms.
                               // When fill is removed from the code,
                               // this all …

我有一个无向且连通（不完整）的顶点图，其中u和v可以是任意 2 个不同的顶点。我想构建从顶点u开始，经过v，然后返回到u 的最小权重电路，而不重复任何边。可以通过执行以下操作来完成吗？

1. 找到从u到v 的最短路径- 称之为p1

2. 从图中删除p1的所有组成边

3. 寻找从v到u 的新最短路径- 称之为p2

4. 将所有删除的边返回到图中，并将p1和p2连接在一起 - 称之为c1

考虑到同时通过u和v的约束，c1是可以构造的最小权重电路吗？如果是的话，我该如何证明，如果不是，为什么不呢？