5 ms·
No, all-pairs shortest path problem is in P as well.
by ondra 17y ago
No, all-pairs shortest path problem is in P as well.
- jws 17y agoI spoke too loosely. Shortest path traversing all nodes is NP (traveling salesman). Obviously shortest path between each pair of nodes is going to be polynomial since the number of pairs is polynomial.