3 ms·
Dijkstra's algorithm gives this as the worst-case performance (via http://en.wikipedia.org/wiki/Dijkstras_algorithm http://en.wikipedia.org/wiki/Dijkstras_algor
by Groxx 17y ago
Dijkstra's algorithm gives this as the worst-case performance (via http://en.wikipedia.org/wiki/Dijkstras_algorithm http://en.wikipedia.org/wiki/Dijkstras_algorithm ), and finds shortest route from a root to all nodes, clearly including the exit:
O( | E | + | V | log | V | )
Definitely not NP-Complete. Finding the distance from all nodes to all other 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.
Granted, the quote only says mazes can 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.