讨论一道最短路径问题

h
hangzhouxi
楼主 (未名空间)

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

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

还是研究一下最短送货途径吧。 亚马逊有算法,给派送人员事先规划了最短途径。 是送几十个包裹的最短途径。还要考虑道路的堵塞情况。 估计每条道路都有堵塞加权。
OverCloud

就是用最短时间送最多的包裹。 有道路长度因素,还有时间因素
q
ql2015

这不是那个谷仓问题吗, divid and conquer
realoption

感觉用两个数列加一次宽度优先搜索就行
两个数列等长于节点数,一个数列保留每个节点距离最近的加油站编号,第二个数列保留离那个加油站的距离,初始化所有距离无穷大,宽度优先相当于动态规划,每一部都更新所有阶段的距离
复杂度O(边数x节点数)

【 在 hangzhouxi () 的大作中提到: 】
: 最近碰到一道题,不知道该用什么方法做比较好。
: 有一个n个点条边的无向图,其中k个点是加油站。现在需要求出n个点中每个点来说距
: 离最近的一个加油站的距离。若这个点是加油站,那么最短距离就是0。数据保证每个
: 点都能至少到达一个加油站。没有负边或者环。
: 我尝试的方法是对于k个加油站每个加油站用一个Dijkstra算法求这个加油站到其它点
: 的最短距离,然后对于每个点来说比较k个最短距离求出真正的最短距离。但时间复杂
: 度太高了。想问一下大家有什么好的想法吗,谢谢