$9\mathrm{.}19\mathrm{.}2$

$9\mathrm{.}39\mathrm{.}4$

$9\mathrm{.}5$

$9\mathrm{.}69\mathrm{.}7$

Find a topological ordering for the graph in Figure $9\mathrm{.}81.$

If a stack is used instead of a queue for the topological sort algorithm in Section $9\mathrm{.}2,$ does a different ordering result? Why might one data structure give a $$better$$ answer?

Write a program to perform a topological sort on a graph.

An adjacency matrix requires O$(|$V$|2)$ merely to initialize using a standard double loop. Propose a method that stores a graph in an adjacency matrix $($so that testing for the existence of an edge is O$(1))$ but avoids the quadratic running time.

a$.$ Find the shortest path from A to all other vertices for the graph in Figure $9\mathrm{.}82.$ b$.$ Find the shortest unweighted path from B to all other vertices for the graph in

Figure $9\mathrm{.}82.$

What is the worst$-$case running time of Dijkstra$$s algorithm when implemented

with d$-$heaps $($Section $6\mathrm{.}5)?$

a$.$ Give an example where Dijkstra$$s algorithm gives the wrong answer in the presence of a negative edge but no negative$-$cost cycle.

$$

b$.$ Show that the weighted shortest$-$path algorithm suggested in Section $9\mathrm{.}3\mathrm{.}3$ works if there are negative$-$weight edges, but no negative$-$cost cycles, and that the running time of this algorithm is O$(|$E$||$V$|).$

A$2$B$2$C $132214$

Exercises $437$s$4$D$3$E$3$F$3$t $6212314$

G$6$H$6$I