Assignment 9
due by the end of class Wednesday March 28 2001.
Recall that in class we covered the following algorithms last week:
- single source shortest path for unweighted digraphs (bfs)
- single source shortest path for weighted digraphs (Dijkstra or Ford)
- all pairs shortest path for weighted digraphs (Floyd)
- topological sorting/ordering
-
Recall that unweighted single source shortest paths
can be computed in linear time.
Briefly describe an algorithm
to compute unweighted shortest paths between all vertex pairs,
and give its complexity (with justification).
-
Recall that transitivity of a relation R means a R b & b R c implies
a R c.
Also recall that to compute the transitive closure of a graph means
to compute all transitive edges and to add them to the graph.
By modifying Floyd's algorithm,
give an efficient algorithm to compute the transitive closure of a graph.
Also, give your algorithm's complexity (justify briefly).
-
How many topological sorts exist for (a) a total order on 7
vertices, and (b) this partial order?
Hint: trace the algorithm from class.
1 2
\ / \
3 4
\ /
5
-
Show or give a counter-example:
(a) Dijktra's algorithm works with negative weighted edges.
(b) Floyd's algorithm works with negative weighted edges.
- Describe briefly how you would solve the following problem:
given a maze constructed from a square grid (empty
locations are represented by spaces, walls by X's,
movement from a location is by one of the four
horizontal/vertical directions),
a starting location S, and a destination D,
describe a shortest sequence of moves which
gets from the start to the finish.
An example is shown below.
XXXXXXXXXXXXXXXXXXXX
X D X
XXXXXXXXXX X X XX
X X XX X XXXX XX
X X X X X X XX
X XX X X X XXXXX
X X SX X X X XX
X X X X X X XX
X X
X XX XXX XX X XXXX
X X
XXXXXXXXXXXXXXXXXXXX
Bonus: how would you solve the problem if the sequence
must encounter *several* destinaion locations (in any order),
and again be a shortest sequence?