我可以帮您翻译成中文。这段内容是关于编程的,讲述了一个最短路径问题需要解决,并且作者相信应该有一种高效的解决方案。接下来是一个图形的 ASCII 表示。
我需要找到从一个“E”点到一个“W”点的最短路径,沿着编号点行走。我们不能在“N”和“S”点上行走。当我们站在一个点上时,我们能够向上、下、左、右走。我需要找到以我步行的编号方块为衡量标准的最短路径。以下是一个更简单的例子: 我会创建一个双向有向无环图,所有边都指向一个编号的边,该编号作为权重,所有指向 E 或 W 的边的权重为 0:
input
. N N N N N N
W 7 9 8 8 7 5 N . . . N N N
W 2 2 2 1 1 6 6 N N N 5 5 N E
W 1 2 3 2 2 2 2 4 5 5 4 2 5 E
. S S S 3 3 3 2 6 5 4 2 2 2 E
. . . . S S 2 2 2 2 3 7 2 2 E
. . . . . . S 2 3 2 7 7 7 7 E
. . . . . . . S 7 7 7 7 7 7 E
. . . . . . . S 7 7 7 S S 7 E
. . . . . . . . S 7 S . . S
. . . . . . . . . S
Output:
35
我需要找到从一个“E”点到一个“W”点的最短路径,沿着编号点行走。我们不能在“N”和“S”点上行走。当我们站在一个点上时,我们能够向上、下、左、右走。我需要找到以我步行的编号方块为衡量标准的最短路径。以下是一个更简单的例子: 我会创建一个双向有向无环图,所有边都指向一个编号的边,该编号作为权重,所有指向 E 或 W 的边的权重为 0:
我的尝试
现在这是一个从多个源到多个汇点寻找最短路径的情况。
我的天真想法是,我可以从每个w运行Dijkstra到每个E。然而,这将以类似于O(W * dijkstra ^ E)(其中E是E节点的数量)的方式运行。
有没有更聪明的方法来执行多源多汇点的Dijkstra算法呢?