From lucia@site.uottawa.ca Sun Nov 9 18:24:44 2003
Date: Sun, 9 Nov 2003 18:23:15 -0500 (EST)
From: Lucia Moura
To: undisclosed-recipients: ;
Subject: A2-Q4: errata
Dear csi4105 students.
There is a mistake in my hints for question 4,
of assignment#2. At this point, I'm not sure
Dijkstra, or some simple adaptation of it, works
for directed acyclic graphs with negative weights.
Anyway, in most textbooks you will see a description
of Dijkstra for graphs with non-negative weights.
However, Bellman-Ford algorithm always work in this
case.
Please, substitute the hint in Q4 by:
"Hint: Review Bellman-Ford algorithm for shortest paths
and note that it works with negative weights for
directed acyclic graphs."
The description of Bellman-Ford is in section 24.1
of the textbook if you would like to take a look at it.
You don't need to describe the algorithm, but you
may call it from the algorithm you are designing.
regards, Lucia