That's not right at all.<p>Dijkstra's for example computes a minimum spanning tree on a graph (it doesn't really compute shortest path from a-&#62;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.