That'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 sho

That'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.