Re: shortest path probl

From: Ahto Truu (ahto.truu_at_mail.ee)
Date: 03/02/04 

Date: Tue, 02 Mar 2004 20:44:11 +0200

> in an undirected graph where edges are labeled with their time and
> cost...
> you can't reach a vertex directly if the cost of the amount of money
> you have is less than the cost of reaching that vertex. everytime you
> pass through an edge you have to pay the cost.
>
> certain given vertexes are "banks" and passing through them will make
> you have as much money as you had initially.
>
> how can i the find minimum initial amount of money you have to have
> so that you obtain the shortest path between a certain source and
> destination ?
>
> any hints ? i think this can be solved somehow by using a modified
> version of Dijkstra's algorithm but i don't know how :(

Unless I completely misunderstand the problem, you could use any
algorithm to find the shortest route, and then, as a separate step,
compute the amount of money you need.

Actually, you need all the shortest routes in case there are several
with the same length, and then you could use some variant of BFS to
select the one with the smallest cost.

Ahto

PS. What bank is it? I'd like to open an account with them before I go
to my around-the-world trip ;)

Relevant Pages