| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > Алгоритмы > Создание карты дорог, и прокладывание маршрута |
| Автор: Obsidian 17.5.2009, 17:50 |
| Есть координаты дорог(созданные с помощью ГИС) в тхт файле в виде 1 точка, 2 точка и т.д. Нужно построить карту из всех этих дорог(с этим все ясно), а вот дальше нужно чтобы пользователь указывал на дороге нач. точку(отправления), проложил маршрут(то есть отметил по какой траектории следует передвигаться) и конечную точку(прибытия) а также посчитать расстояние маршрута. как все это можно реализовать и с помощью каких средств? расстояния нужно учитывать для решения транспортной задачи, так что маршрутов нужно несколько сразу делать |
| Автор: MasterOfCode 18.5.2009, 05:58 |
| Какую ГИС систему вы используете? |
| Автор: ILAgent 18.5.2009, 14:46 |
| DELETED |
| Автор: Earnest 18.5.2009, 15:27 |
| Это задача на графы: поиск кратчайшего пути, вес == длина дороги. Т.е. тебе для начала нужно собрать дороги в граф. |
| Автор: maxdiver 18.5.2009, 18:25 |
| См. алгоритм Дейкстры (находит кратчайшие пути из одной какой-то вершины до всех остальных) или Флойда (находит кратчайшие пути от каждой до каждой вершины), также известен алгоритм Форда-Беллмана (результат такой же, как у Дейкстры, но помедленней работает). |
| Автор: Earnest 19.5.2009, 07:56 |
| Белман вроде для случаев, когда вес может уменьшаться, т.е. есть ребра с отрицательными весами, а в данной задаче нет смысла... |
| Автор: nworm 20.5.2009, 06:58 |
| Дополнение. Если надо несколько маршрутов, то надо искать k кратчайших путей. |
| Автор: KpoHyc 8.8.2009, 02:29 | ||
Если еще интересно у меня есть готовое решение для поиска кратчайшего пути в подобном графе.
|