从城市到加油站的最短路径(无燃料，但道路加权)

Question

在有向图中，边上有权重，表示节点之间不同道路的长度。一些节点是加油站，其他的是城市。我怎样才能找到离每个城市最近的加油站？燃料没有问题。权重就是节点之间道路的长度。

我想在每个不是加油站的节点(N1，N2，...)中使用Dijkstra。并且通过对每个节点具有关键字" true "，"False"，如果它是加油站(G1，G2，...，)则具有真，然后将具有关键字“True”的最近节点(Ni)返回到某个加油站(Nj)。

不确定它的复杂性。它看起来像O(Dijkstra * size of (N1，N2，...))，然后对于每个Ni，线性遍历数组并返回具有"True“键的最小节点。不确定这是否是一种有效的方法，我想得到一些帮助，也许是更有效的方法。

Answer 1

这个问题可以只使用Dijkstra算法的一次运行来解决，但需要一个扭曲。虽然通常在实现Dijkstra时，您只对开始时的一个顶点设置零距离，但要解决此问题，您需要为所有加油站的顶点设置零距离。因此，您还需要在初始化时将这些零距离顶点添加到优先级队列(堆)。除了初始化算法保持不变。