algorithm - 针对具有矩阵的极稠密图优化的 dijkstra 算法

Question

您有 N 个节点，标记为 1…N (N <= 50000)。每个节点都有一个指定的 ID，范围为 1…M，其中 M 最多为 50。您正在尝试找到从 1 到 N 的最短路径。

还给你一个矩阵 M x M，以确定不同 ID 的节点之间是否存在有向边。如果 ID i 的节点有指向 ID j 的节点的有向边，则 M_ij = ‘Y’，否则为‘N’。请注意，M_ij 可能不等于 M_ji，并且 M_ii 可能 = 0。

如果两个节点之间存在边，那么它们之间的有向边的权重就是它们标签之间的差。

例子:

有5个节点。

节点 1:ID 1

节点 2:ID 4

节点 3:ID 2

节点 4:ID 3

节点 5:ID 4

矩阵:

云云

新年快乐

纽约

尼恩

所以在这个矩阵中，我们知道 ID 1 的节点有指向 ID 1 和 ID 3 的节点的边。ID 2 的节点有指向 ID 4 的节点的边。ID 3 的节点有指向 ID 的节点的边ID 2 和 ID 3。ID 4 的节点有指向 ID 2 的节点的边。

答案 = 6。

节点 1 和 5 之间的最短路径是通过从节点 1 到节点 4 的有向边，权重为 4 - 1 = 3。请注意，这条边是可能的，因为节点 1 的 ID 为 1，而节点 4 为ID 3，ID 1 的节点有指向 ID 3 的所有节点的边。接下来，您将使用从节点 4 到节点 3 的有向边，权重为 4 - 3 = 1；然后是从节点 3 到节点 5 的有向边，权重为 5 - 3 = 2。3 + 1 + 2 = 6，因此总的最短路径为 6。

我的解决方案:

当我第一次看到这个问题时，我认为 Dijkstra 的算法可以很容易地解决它。然而，它的时间复杂度是N^2logN，边的数量最多为50000^2，这太高了。如何解决密集图中的最短路径问题？有没有办法通过某种方式利用矩阵来优化 Dijkstra？

Answer 1

假设有 3 个具有不同标签的节点共享相同的 id 1:
ID 1 <==> Labels {1, 7, 13}

同理，有5个节点共享同一个id2:
ID 2 <==> Labels {2, 8, 12, 15}

共享相同id的3个节点3:
ID 3 <==> Labels {5, 10, 11}

和共享相同id的2个节点4:
ID 4 <==> Labels {6, 9}

现在假设我们有 4 条边:

• ID1 -> ID2
• ID1 -> ID3
• ID2 -> ID4
• ID3 -> ID4

如果我们想找出标签“7”和“9”之间的最小距离，我们该怎么做？

标签 7 表示 ID1，标签 9 表示 ID4。这意味着我们需要找到 ID1 和 ID4 之间的最短距离。

但由于这 2 个 ID 之间没有直接边，我们必须先跳转到 ID 2 或 3。

让我们计算到 ID 2 的距离:
我们应该从 ID1 跳转到 ID2 中的哪个标签？
由于距离定义为 2 个标签值之间的绝对差，并且源标签为“7”，我们应该跳转到最接近 7 的标签。
在 {1, 2, 8, 12, 15} 中，这将是 '8'(距离 = 8-7 = 1)

让我们计算到 ID 3 的距离:
我们应该从 ID1 跳转到 ID3 中的哪个标签？
在 {5, 10, 11} 中，最接近 7 的数字为 '5'(距离 = 7-5 = 2)

由于到 ID2 的距离小于 ID3，我们应该跳转到 ID2，标签 8。

现在我们在标签8，我们可以直接跳转到ID4中的标签9(距离=9-8=1)

总距离 = 1 + min(1, 2) + 1 = 3

一般的算法是:

• 在 ID 和共享该 ID 的标签的排序列表之间创建 HashMap 。
• 如果源标签为 L1，目标标签为 L2，假设它们属于 ID I1 和 I2，执行 dijkstra 以找到 ID I1 和 I2 之间的最短距离。
• 在执行 dijkstra 时，通过在共享该 id 的标签列表中选择值最接近 L1 的标签来计算当前标签“L1”和邻居 id 之间的“距离”(可以从 hashmap 访问此列表).
• 对于从 L1 到邻居 ID 的所有此类距离，将所有这些距离(连同所选标签)推送到优先级队列(与普通 dijkstra 相同)。

在排序数组中查找最接近某个值的数字 can be done in O(logn) , 其中 n 是 已排序数组的大小。

dijkstra 的算法复杂度为 O(M^2 * logM * logX) ，其中 X = 共享单个 ID 的标签的平均数量，可以安全地假设为 N/M。

创建带排序列表的 hashmap 需要 O(M*X*logX) = O(N * logN/M)复杂性。

所以总复杂度 = O((N * log(N/M)) + (M^2 * logM * log(N/M)) ~ O(log(N/M) * (N + M^2)