Consider the following digraph:

Numbers on arcs represent costs.

(a) Find (by inspection) shortest paths from node 1 to all other nodes.

(b) Enumerate the dicycles of the graph.

(c) Determine whether each dicycle is a negative dicycle.

(d) How does the presence of negative dicycles in this instance make it more difficult for an algorithm to compute shortest paths?

Transcribed Image Text:

3 -5 1 2 10 -20 40 2