алгоритм Дейкстры на iOS

Я отслеживаю местоположения и их связи с другими местоположениями.
Я храню местоположения в NSArray, в то время как каждое местоположение представлено в виде словаря. Каждое местоположение имеет Словарь с атрибутами (locationName, Connections, latitude, longitude), где Connections — это массив других местоположений, с которыми это местоположение связано (не из). Я использую широту/долготу и алгоритм Хаверсина для определения расстояния между двумя точками.

ДАЛЕЕ, я хотел бы использовать алгоритм кратчайшего пути Дейкстры, чтобы найти кратчайший путь между источником и местом назначения (источник и место назначения выбираются пользователем)

Это не для коммерческого использования и не требует поддержки сотен или тысяч местоположений.

Я ищу некоторый объективный код C, который будет выполнять этот поиск.


ios graph dijkstra
person user1278974    schedule 06.06.2012    source источник
comment
Мы не будем писать ваш код за вас, но если вы предоставите нам то, что у вас есть, мы можем дать предложения.   -  person SomeKittens    schedule 06.06.2012
comment
Я понимаю. Передавая параметры источника, назначения и LocationArray, я хочу вернуть кратчайший путь (с точки зрения расстояния) между ними. Каждое соединение является «односторонним», A--->B означает, что вы можете добраться до B из A, но не подразумевается, что вы можете добраться от B до A, если это явно не определено в словаре местоположений B. Я думаю, это может стать более запутанным, если я поделюсь своим текущим неработающим кодом. Эту часть (алгоритм Дейкстры) нужно переписать.   -  person user1278974    schedule 06.06.2012
comment
Идите вперед и поделитесь им (плохой код не означает, что вы плохой программист, это просто означает, что вы учитесь). В Википедии есть отличный пример псевдокода. en.wikipedia.org/wiki/Dijkstra's_algorithm   -  person SomeKittens    schedule 06.06.2012
comment
Спасибо Котята. Я просто думаю, что сосредоточение внимания на том, что у меня есть, будет отвлечением прямо сейчас. У меня есть рекурсивная версия, которая является неправильным подходом - я сделал это до того, как обнаружил существование Дейкстры. Так что он домашний. Его нужно выбросить и переписать, чем я сейчас и занимаюсь.   -  person user1278974    schedule 06.06.2012

Ответы (3)


arrow_upward
4
arrow_downward

Быстрый поиск в Google нашел некоторый код Objective-C по адресу snyderp/PESGraph, в котором говорится:

PESGraph — это простая реализация графа для Foundation.kit, которая позволяет создавать структуры узлов и путей, а затем находить кратчайший путь между ними. Он включает в себя модульные тесты, которые также предоставляют несколько примеров того, как использовать код.

Также этот вопрос ранее задавался на SO «>есть-простой-способ-применить-кратчайший-путь-алгоритм-в-цели-c, и решение указывало на тот же репозиторий git, который я нашел через google.

person Peter M    schedule 06.06.2012
comment
Спасибо за совет Петр. - person user1278974; 07.06.2012
comment
В репозиторий PESGraph нет примера кода. Удалось ли вам на самом деле использовать его в конце? - person inigo333; 19.09.2016

arrow_upward
2
arrow_downward

Мне пришлось написать свой собственный пример кода, потому что я не смог найти ни одного хорошего и работающего примера. Вы можете проверить это здесь:

https://github.com/aolszak/AOShortestPath

person ArturOlszak    schedule 25.08.2014

arrow_upward
0
arrow_downward

Бессовестная вилка: mj-dijkstra Представление графа — это NSDictionary или объект, который ведет себя как словарь.

person dmitri    schedule 03.05.2013