Re: A question about Dijkstra's algorithm
From: A. G. McDowell (mcdowella_at_nospam.uk)
Date: 01/19/04
- Next message: Bilal Sallakh: "Re: A question about Dijkstra's algorithm"
- Previous message: Bilal Sallakh: "Linear programming vs. Graph Algorithms"
- In reply to: Bilal Sallakh: "A question about Dijkstra's algorithm"
- Next in thread: Bilal Sallakh: "Re: A question about Dijkstra's algorithm"
- Reply: Bilal Sallakh: "Re: A question about Dijkstra's algorithm"
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]
Date: Mon, 19 Jan 2004 06:11:06 +0000
In article <d5fb3df3.0401180930.72d789dc@posting.google.com>, Bilal
Sallakh <afkar@mail2world.com> writes
>Given a directed acyclic graph with all edges have negative weights.
>
>Can we modify dijkstra's shortest path algorithm to find the shortest
>path in such a
>
>graph?
>
>That is equivilant to:
>Can we modify dijkstra's shortest path algorithm to find the longest
>path in a direct
>
>acyclic graph with all edges have positive weights?
>
>I know that in both cases a linear algorithm suffices where we "relax"
>the edges of
>
>the vertices taken into topological order -The so called Bellman
>Algorithm. But I'm
>
>discussing Dijkstra's.
>
>
>Also I expect that no modification can be found.
>
>But our instructor insists that some modifications can make dijkstra's
>algoirthm work.
>
>He claims that he read that in an old reference.
>
>
>Regards.
The Algorithm Design Manual, by Skiena, claims (section 8.4) "If your
graph has edges with negative weights, you must use the more general but
less efficient Bellman-Ford algorithm" (see e.g. the massive MIT book -
if there are no -ve cycles this returns shortest path info otherwise it
tells you which nodes have -ve cycles through them).
-- A. G. McDowell
- Next message: Bilal Sallakh: "Re: A question about Dijkstra's algorithm"
- Previous message: Bilal Sallakh: "Linear programming vs. Graph Algorithms"
- In reply to: Bilal Sallakh: "A question about Dijkstra's algorithm"
- Next in thread: Bilal Sallakh: "Re: A question about Dijkstra's algorithm"
- Reply: Bilal Sallakh: "Re: A question about Dijkstra's algorithm"
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]
Relevant Pages
|
