top | item 1053228 (no title) ondra | 16 years ago No, all-pairs shortest path problem is in P as well. discuss order hn newest jws|16 years ago I 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.
jws|16 years ago I 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.
jws|16 years ago