具有多个源和汇的寻路？

Question

我有一个需要解决的最短路径问题，并且我相当确定应该有一个有效的解决方案\n我有一个有趣的图形表示：

\n

作为ascii：

\n

input\n\n. N N N N N N\nW 7 9 8 8 7 5 N . . . N N N\nW 2 2 2 1 1 6 6 N N N 5 5 N E\nW 1 2 3 2 2 2 2 4 5 5 4 2 5 E\n. S S S 3 3 3 2 6 5 4 2 2 2 E\n. . . . S S 2 2 2 2 3 7 2 2 E\n. . . . . . S 2 3 2 7 7 7 7 E\n. . . . . . . S 7 7 7 7 7 7 E\n. . . . . . . S 7 7 7 S S 7 E\n. . . . . . . . S 7 S . . S\n. . . . . . . . . S\n\nOutput:\n35\n

\n

我需要找到从“E”点之一到“W”点之一的最短路径，走过编号的点。我们无法在“N”和“s”点上行走。当我们站在一个地方时，我们\xc2\xb4能够上下左右行走。我需要根据我正在行走的编号方块找到最短路径。这是一个更简单的例子：

\n

\n

我将创建一个双向 DAG，其中所有边都朝向编号边，以该编号作为权重，并且所有边都朝向 E 或 W，权重为 0：

\n

\n

我的尝试

\n

现在这是一个寻找从多个源到多个接收器的最短路径的情况。\n我天真的想法是我可以从每个 w 到每个 E 运行 Dijkstra。然而，这会以类似 O(W*dijkstra^E) 的方式运行（其中E是E节点的数量）

\n

有没有更聪明的方法来实现多源多接收器 dijsktra？

\n

Answer 1

经过一番思考后，我想我自己已经找到了解决方案。接受的答案是完全有效且良好的，但我认为应该比 A bfs 运行得更快，在最坏的情况下需要评估每个边 E 次。

如下：我将所有 E 节点与源连接，边从源 (s) 到 E，权重为 0。所有 W 节点也连接到接收器 (t)，边从 W 到接收器。

这意味着之前显示的图表将如下所示：

现在我应该能够从 s 到 t 运行常规的 ol' dijkstra