Путь комплексного пути

Question

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

Я надеюсь, что этот небольшой рисунок поможет передать то, что я пытаюсь сделать.

У меня есть список из 7 000 мест, каждый из которых имеет неопределенное, но небольшое количество дверей. Каждая дверь является мостом между обоими местами.

Ссылка на приведенную выше диаграмму, как бы я нашел поиск самого быстрого маршрута через двери, чтобы добраться от А до Я?

Мне не нужен полный источник, просто код psuedo будет в порядке.

Очевидно, вы можете взять A -> B -> C -> D -> G -> X -> L -> Z, , но самый короткий маршрут - A -> B -> C -> K -> X -> Z.

Answer 1

Представьте ваши местоположения как узлы и двери как ребра на графике. Затем примените несколько стандартных shortest path algorithm(s), и все готово.

Answer 2

Посмотрите на Pathfinding алгоритмы в Википедии. Вы в основном создаете серию узлов и соединений между ними, и алгоритм работает через них, находя путь от начала до цели.

Answer 3

Можно предположить, что каждый номер является узлом, и каждая дверь является узлом, и проблема будет найти кратчайший путь в графе, который вы можете найти с Dijkstra's algorithm, например

Answer 4

Если у вас есть эвристический, который может сделайте разумное предположение относительно лучшего узла, чтобы попробовать дальше, тогда вы можете использовать алгоритм A *. У меня есть реализация C# в моем блоге; не стесняйтесь использовать код. Учитывая правильную эвристику, A * может быть немного более эффективным, чем другие алгоритмы поиска пути.

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