One kind of graph for which Dijkstra's Algorithm won't be able to find shortest paths is the first one we saw in the notes.

Not only is this graph problematic for Dijkstra's Algorithm; it's problematic in general, because it contains a negative-weight cycle.

But what about a directed acylic graph that contains exactly one negative-weight edge somewhere? Suppose we wanted to find all shortest paths from some vertex in that graph. By definition, we're no longer solving the positive-weighted single-source shortest-path problem. But could Dijkstra's Algorithm always find the shortest paths in such a graph?

• If so, then what additional characteristic would the graph need to have before Dijkstra's Algorithm would certainly fail to find the shortest paths?
• If not, then show one example graph meeting this characteristic for which Dijkstra's Algorithm could not find the shortest paths. Demonstrate your answer by showing the table of k, d, and p values for each vertex at each step, as we saw in the Shortest Paths notes.