Shortest path on a general graph

• A

  Because shortest path has no optimal substructure

• B

  Because cycles mean the vertices have no order that respects the dependencies

• C

  Because the number of vertices is usually too large to store

• D

  Because the weights can differ, which means the subproblems are not comparable