No, all-pairs shortest path problem is in P as well. | Hacker News

Hacker Newsnew | past | comments | ask | show | jobs | submit

		ondra on Jan 14, 2010 \| parent \| context \| favorite \| on: Oil Drop Navigates Complex Maze No, all-pairs shortest path problem is in P as well.

jws on Jan 14, 2010 [–]

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.

Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact