algorithm - 将点网络的“路径”连接成“路线”

Question

我有一个名为paths.

paths =  1 2
         1 3
         1 4
         2 3
         2 5
         3 4
         3 5

每个元素都是矩阵中二维坐标的索引Crdnts。每行paths表示该行中的两个点通过“路径”连接。

例如，如第一行所示，Crdnts(1,:)连接到Crdnts(2,:)。

我想创建一个称为routes将所有路径连接到“路线”的矩阵（从第 1 点开始）

使用paths上面的矩阵，routes将是

routes = 1 2 3 4
         1 2 3 5
         1 2 5 *
         1 3 4 *
         1 3 5 *
         1 4 * *

我应该指出几个问题：

1. 通常有大约 1000 个坐标Crdnts。
2. 路线可以有不同的大小（参见示例 *）。有些可能有 100 条路径，有些只有 1 条。因此，单元阵列可能比矩阵更好。

我正在寻找一种方法来做到这一点，而无需使用太多的 for 循环，因为这需要很多时间来处理许多点/路径。我无意寻找“最短路线”等。感谢您的帮助。

Answer 1

Tardos 的 Kleinberg 的算法设计第 6.1 节描述了与此等价的区间调度问题。