To assess how $$well$-$connected$$ two nodes in a directed graph are, one can not only look at the length of the shortest path between them but also count the number of shortest paths.

This turns out to be a problem that can be solved efficiently, subject to some restrictions on the edge costs. Suppose we are given a directed graph G $=($V$,$E$),$ with costs on the edges; the costs may be positive or negative, but every cycle in the graph has strictly positive cost. We are also given two nodes v$,$ w in V$.$ Regarding question $6,$ why can$$t an algorithm for this problem be adopted to output the paths themselves, instead of just the number of paths?

Group of answer choices

a$)$ Because there are polynomially many such paths, but it takes exponential time to find them.

b$)$ Because there may be exponentially many such paths.

c$)$ Because the number of such paths can be much smaller than the size of the graph itself, and so can be computed in polynomial time.

d$)$ Because different paths have different costs, and so one would need to take this into account.