Применение алгоритма кратчайшего пути по городам

Question

У меня есть 6 городов в моем отчете. Мумбаи, Брук, Хбад, Дели, Ченнай, Пуна. И запись указана для каждого города.

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

С IP-адреса пользователя я могу получить его местоположение (город или язык-лати). Я думал рассчитать расстояние пользователя с каждым из вышеперечисленных городов. То, что ближайше, я должен выбрать, чтобы показать запись.

Любой лучший способ сделать это? Я работаю с php.

Пожалуйста, поговори на уровне реализации ...

Answer 1

Вы можете представлять свои города в качестве узлов графа и расстояния между ними, как вес по краям, и чем применить алгоритм Дейкстры (http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm) Если вы хотите получить 5 лучших короткие расстояния вы можете использовать один из алгоритма йены или A * (* http://en.wikipedia.org/wiki/A _search_algorithm)

LE: вы должны создать взвешенный граф (ориентированный или нет, зависит от вас). Узел на графике может быть именем города (или если у вас есть более подробная информация о городе, вы можете использовать объект типа Город). Расстояние между городами будет представлено взвешенным краем между ними.

Запуск Dijkstra, вам нужно будет указать начальный узел и конечный узел (в ваших кассах город, в котором находится ваш пользователь в тот момент, и город, куда он хочет пойти). Алгоритм вернет кратчайшее расстояние, а небольшая реализация может распечатать весь путь от источника к месту назначения.