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 <lucia@site.uottawa.ca>
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