讨论一道最短路径问题

最近碰到一道题，不知道该用什么方法做比较好。
有一个n个点条边的无向图，其中k个点是加油站。现在需要求出n个点中每个点来说距离最近的一个加油站的距离。若这个点是加油站，那么最短距离就是0。数据保证每个点都能至少到达一个加油站。没有负边或者环。

我尝试的方法是对于k个加油站每个加油站用一个Dijkstra算法求这个加油站到其它点的最短距离，然后对于每个点来说比较k个最短距离求出真正的最短距离。但时间复杂度太高了。想问一下大家有什么好的想法吗，谢谢

玛玛哈哈 发表于 2021-1-29 03:52
感谢回复，我觉得这个可行，我去试一下

其实实现的时候完全没必要把这个虚拟节点给弄出来。第一步用Dijkstra的时候，直接把所有加油站扔进heap里面，每个距离都是0就好了。也类似于多起点的Dijkstra，也有点像平时会用到的多起点BFS。

不知道小帅 发表于 2021-1-29 03:57
其实实现的时候完全没必要把这个虚拟节点给弄出来。第一步用Dijkstra的时候，直接把所有加油站扔进heap里 ...

聪明，蹲一波其他人的代码一会来学习下。

玛玛哈哈 发表于 2021-1-29 03:41
n最多有50000个点，n^3的时间复杂度可能承受不起

这肯定是不行的。其实这个题目有个trick，你假设一个虚拟节点，这个节点到所有加油站的距离都是0。这样子的话，从这个虚拟的点到每个点的距离，就是那个点到加油站的最短距离。可以仔细品一下。

感觉像bellman ford 算法？

这个是multi source shortest path
使用Floyd warshall就可以了

shaoli12800 发表于 2021-1-29 03:32
感觉像bellman ford 算法？

Floyd warshall

红A 发表于 2021-1-29 03:38
这个是multi source shortest path
使用Floyd warshall就可以了

n最多有50000个点，n^3的时间复杂度可能承受不起

shaoli12800 发表于 2021-1-29 03:32
感觉像bellman ford 算法？

这个是没有负权重的边的

红A 发表于 2021-1-29 03:38
这个是multi source shortest path
使用Floyd warshall就可以了

其实没必要，速度会略慢。假设一个虚拟节点，到所有加油站距离都是0。这样的话只需要求以这个虚拟节点为起点，到所有节点的最短路径。这个最短路径，就是这些节点到加油站的最短距离。

不知道小帅 发表于 2021-01-28 11:48:06
这肯定是不行的。其实这个题目有个trick，你假设一个虚拟节点，这个节点到所有加油站的距离都是0。这样子的话，从这个虚拟的点到每个点的距离，就是那个点到加油站的最短距离。可以仔细品一下。

感谢回复，我觉得这个可行，我去试一下