Dijkstra's algorithm gives this as the worst-case performance (via <a href="http://en.wikipedia.org/wiki/Dijkstras_algorithm" rel="nofollow">http://en.wikipedia.org/wiki/Dijkstras_algorithm</a> ), and finds shortest route from a root to all nodes, clearly including the exit:<p><pre><code>  O( | E | + | V | log | V | )
</code></pre>
Definitely not NP-Complete.  Finding the distance from <i>all</i> nodes to <i>all other</i> nodes may be NP-Complete (not sure, but it seems like it would be, and doing so would be meaningless in a maze), but maze-solving is relatively easy in computing terms.  Heck, even if you don't know the maze it's not NP-Complete: simply walk the whole thing and then calculate the shortest path.<p>Granted, the quote only says mazes <i>can</i> fall into NP-Complete... but I really don't know what you'd have to do to do that, without clearly falling out of a "maze" problem and into a more general "graph" problem.