Complex pathing route

Question

                      L->|
  A -> B              ^  |
  |__> C -> D-> G->X--|  |
       K    |_> T  |  |_>Z
       |___________|

I hope this small drawing helps convey what I'm trying to do.

I have a list of 7,000 locations, each with an undefined, but small number of doors. Each door is a bridge between both locations.

Referencing the diagram above, how would I go about finding the quickest route through the doors to get from A to Z?

I don't need full on source, just psuedo code would be fine.

Obviously you can take A -> B ->C -> D -> G -> X -> L -> Z, but the shortest route is A -> B -> C -> K -> X -> Z.

Answer 1

Look up Pathfinding algorithms on Wikipedia. You basically build up a series of nodes and connections between them, and the algorithm works through them finding a way from the start to a goal.

Answer 2

Represent your locations as nodes and the doors as edges in a graph. Then apply some rather standard shortest path algorithm(s) and you're done.

Answer 3

You can suppose that each room is a node and each door is a node and the problem will become finding shortest path in graph which you can find with Dijkstra's algorithm for example

Answer 4

If you have a heuristic that can make a reasonable guess as to the best node to try next, then you can use the A* algorithm. I have a C# implementation of it on my blog; feel free to use the code. Given a correct heuristic, A* can be quite a bit more efficient than other path finding algorithms.

http://blogs.msdn.com/ericlippert/archive/tags/AStar/default.aspx