4 ms·
Shortest path from one point to another in a graph is polynomial. Shortest path to all nodes is NP complete.
by jws 17y ago
Shortest path from one point to another in a graph is polynomial. Shortest path to all nodes is NP complete.
- ondra 17y agoNo, 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.
- elblanco 17y agoThat's not right at all. Dijkstra's for example computes a minimum spanning tree on a graph (it doesn't really compute shortest path from a->b, it computes shortest path from a to all other nodes) and does it in O(E+VlogV) if I remember....which is quite a bit better than polynomial time.