具有边缘成本的Dijkstra最短路径算法 [英] Dijkstra shortest path algorithm with edge cost

问题描述

我有一个有向图，正加权图。每个边缘都有使用成本。
我只有一个钱，我想用dijkstra算法计算最短路径，但是路线上的边成本之和必须小于或等于A。

I have a directed, positive weighted graph. Each edge have a cost of use. I have only A money, i want to calculate shortest paths with dijkstra algorithm, but sum of edges costs on route must be less or equal to A.

我想用最小的Dijstra修改来做到这一点（如果我可以用Dijkstra的小的修改来做到这一点）。如果可以，我必须在 O（n * log（n））中执行此操作，但是我认为可以。

I want to do this with most smallest Dijstra modification (if I can do it with small modification of Dijkstra). I must do this in O(n*log(n)) if I can, but i think i can.

有人可以帮助我吗？

推荐答案

https://www.spoj.pl/problems/ROADS/

问题出在< a href = http://www.hsin.hr/ceoi98/ rel = nofollow noreferrer> CEOI '98 及其官方解决方案可以在此处。

The problem was given at CEOI '98 and its official solution can be found here.

这篇关于具有边缘成本的Dijkstra最短路径算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！