一种使用Dijkstra计算的算法
An algorithm using Dijkstra to calculate
给定的是一个有向图 G = (V, E)，正边权重 w:E 到 R+。
该图表示布鲁克林的道路，每条边上的权重表示道路的长度（以英里为单位）。奖品放在节点 t（在 V 中）。给定的是V中的一组节点A（A是V的一个子集），以及一个s:A到R+.
的函数
在A中的每个v中都有一个玩家。游戏开始，所有玩家同时出发，前往奖品。
每个玩家都以最短路径从其起始节点到 t。离开节点 v 的玩家以恒定速度 s(v) 前进，
即，对于 E 中的每个 e，该玩家需要 w(e)/s(v) 个时间单位才能过马路 e。
提出一个 returns 获胜者的有效算法。
我的尝试：
算法：
- 运行 Dijkstra 在A中的某个节点v上，并发起一个大小为|A|的数组（对于每个玩家）。
- 对于A中的每个v，迭代从v到t的最短路径，并在每次迭代中将w(e)/s(v)添加到数组中该特定节点的总和。
- Return数组的最小值。
我觉得这个可以改进，比如把数组换成其他数据结构，这样最后一步效率会更高，但我不知道怎么做。
如有任何帮助，我将不胜感激！
谢谢！
您可以通过 运行 Dijkstra 算法一次从目标节点 t 计算所有最短路径 to/from t。您正在寻找 a ∈ A 中 Distance(a, t) / Speed(a) 的最小值，其中 Distance 是 Dijkstra 算法的标准边权和。由于原始图形是有向的，因此您需要先反转所有边的方向并处理该图形。
如果 'A' 很小，您偶尔可以通过在访问 A 中的所有节点后立即停止 Dijkstra 算法来稍微优化一下，尽管最坏情况下的运行时间是一样。
给定的是一个有向图 G = (V, E)，正边权重 w:E 到 R+。
该图表示布鲁克林的道路，每条边上的权重表示道路的长度（以英里为单位）。奖品放在节点 t（在 V 中）。给定的是V中的一组节点A（A是V的一个子集），以及一个s:A到R+.
的函数在A中的每个v中都有一个玩家。游戏开始，所有玩家同时出发，前往奖品。
每个玩家都以最短路径从其起始节点到 t。离开节点 v 的玩家以恒定速度 s(v) 前进， 即，对于 E 中的每个 e，该玩家需要 w(e)/s(v) 个时间单位才能过马路 e。
提出一个 returns 获胜者的有效算法。
我的尝试：
算法：
- 运行 Dijkstra 在A中的某个节点v上，并发起一个大小为|A|的数组（对于每个玩家）。
- 对于A中的每个v，迭代从v到t的最短路径，并在每次迭代中将w(e)/s(v)添加到数组中该特定节点的总和。
- Return数组的最小值。
我觉得这个可以改进，比如把数组换成其他数据结构，这样最后一步效率会更高，但我不知道怎么做。
如有任何帮助，我将不胜感激！
谢谢！
您可以通过 运行 Dijkstra 算法一次从目标节点 t 计算所有最短路径 to/from t。您正在寻找 a ∈ A 中 Distance(a, t) / Speed(a) 的最小值，其中 Distance 是 Dijkstra 算法的标准边权和。由于原始图形是有向的，因此您需要先反转所有边的方向并处理该图形。
如果 'A' 很小，您偶尔可以通过在访问 A 中的所有节点后立即停止 Dijkstra 算法来稍微优化一下，尽管最坏情况下的运行时间是一样。