两个顶点之间具有平行边的 Dijkstra

Question

我遇到了一个路由问题，我需要在两点之间检索最佳的 n 个解决方案。我正在使用 Dijkstra 来获得最佳解决方案，并在此基础上使用 Yen Top K 算法来获得 n 个最佳解决方案。

然而，它有一个扭曲，顶点之间可以有多个平行边。让我们想象一个公交网络：

Line A: a -> b -> c -> d -> e
Line B: b -> c -> d -> e -> f
Line C: a -> b -> c -> g -> h

构建图形时，如何处理这些并行连接？我正在考虑像这样构建图表：

Line A: a->b,a->c,a->d a->e,b->c,b->d,b->d,b->e,c->d,c->e,d->e
Line B: b->c,b->d,b->e,e->f,c->d,c->e,c->f,d->e,d->f,e->f
Line C: a->b,a->c,a->g,a->h,b->c,b->g,b->h,c->g,c->h,g->h

因此，当我不必换乘公共汽车时，我有直接的优势。对于我经过的每个顶点，我添加一个连接惩罚权重。

因此，如果我想从 a->e 出发，我可能会得到 A 线，因为使用 C 线 a->b，B 线 b->e 可能会更长，因为连接时间，即使时间线C a->b和B线b->e可能比A线快

但是我仍然需要处理并行连接。所以我想我需要按重量对平行边进行排序。

目前这是基于静态时间信息，但在某些时候它应该考虑实际的时间安排信息。并且取决于您在两个顶点之间的权重可能会发生变化。例如。当你到达 b 点时，通过 C 线的最快连接将不再是最快的，因为你会错过 C 线等。

是否有任何资源可以解释您将如何处理这些更复杂的情况？

Answer 1

一种方法是通过 "splitting nodes"

将问题还原为一个简单的图（无平行边）

这意味着，如果您有一个节点 u，边 (v,u)_1, (v,u)_2, ..., (v,u)_k，您可以将 u 拆分为：u, u_1, u_2,...,u_k，边：(u_1,u), (u_2,u), ..., (u_k,u), (v,u_1), (v,u_2), ...., (v,u_k)，以及权重： w(u_i,u) = 0 for all i 和 w(v,u_i) = w((v,u)_i) for all i

现在您可以运行轻松地为简单图设计任何算法，其中顶点数以平行边数的线性因子增加。

两个顶点之间具有平行边的 Dijkstra

Dijkstra with parallel edges between two Vertices

algorithm

routing

dijkstra