Алгоритм дейкстры

The real -=LOGAN-=

T
Статус: Offline
Реєстрація: 04.07.2008
Повідом.: 675
  • 🟢 11:57 Відбій тривоги в м. Харків та Харківська територіальна громада.Слідкуйте за подальшими повідомленнями.#м_Харків_та_Харківська_територіальна_громада
  • #1
Алгоритм дейкстры

Добрый вечер.
Подскажите как реализовать данный расчет расстояний?
Пример:
⚠ Тільки зареєстровані користувачі бачать весь контент та не бачать рекламу.

Я так понимаю у меня должно быть в БД город Харьков который соединяется со всеми маленькими (песочин,валки, и тд) и точно так же у Киева.
Ей богу не понимаю как должно быть все организовано в БД.
Подскажите структуру таблицы подходящую для этой задачи.
 
  • 🟢 11:57 Відбій тривоги в м. Харків та Харківська територіальна громада.Слідкуйте за подальшими повідомленнями.#м_Харків_та_Харківська_територіальна_громада
  • #2
запись в бд: имя_значимой_точки, координаты, другая_важная_инфа (типа вектор направления, ближайшие связи и т.д.)

а расчет расстояний на лету, получил 2 точки и погнал считать
 
  • 🟢 11:57 Відбій тривоги в м. Харків та Харківська територіальна громада.Слідкуйте за подальшими повідомленнями.#м_Харків_та_Харківська_територіальна_громада
  • #3
1. Харьков, автомагистраль, (песочин 10,люботин 20,мерефа 30, покотиловка 40)
2. Киев, автомагистраль, (Счастливое 50,Малая Александровка 60)
p.s. цифры это как километры, но конечно будет другая таблица.
А почем мне тогда считать в алгоритме дейкстры?километраж?
Какой у меня размер матрицы?
 
  • 🟢 11:57 Відбій тривоги в м. Харків та Харківська територіальна громада.Слідкуйте за подальшими повідомленнями.#м_Харків_та_Харківська_територіальна_громада
  • #4
алгоритм тебе для того чтобы найти кратчайший путь, все узлы собери с координатами, по координатам считай по алгоритму куда как проехать, потом каждую пару координат преобразуй в километры

что за матрица не представляю) видимо границы координат, по 360 градусов
 
  • 🟢 11:57 Відбій тривоги в м. Харків та Харківська територіальна громада.Слідкуйте за подальшими повідомленнями.#м_Харків_та_Харківська_територіальна_громада
  • #5
Если буду по координатам тогда я потеряю просчет по автомобильным трассам. То есть как я понял должно быть так : каждый город должен быть в связях и километраж между ними?
 
  • 🟢 11:57 Відбій тривоги в м. Харків та Харківська територіальна громада.Слідкуйте за подальшими повідомленнями.#м_Харків_та_Харківська_територіальна_громада
  • #6
да, если считаешь для самолетов и точки это аэропорта, для машины точки это изменение направления дороги для каждой дороги разный коэффициент, но большинство считают их прямыми, погрешность небольшая, а экономия производительности существенная, ну кроме кольцевых дорог, но их не так много
 
  • 🟢 11:57 Відбій тривоги в м. Харків та Харківська територіальна громада.Слідкуйте за подальшими повідомленнями.#м_Харків_та_Харківська_територіальна_громада
  • #7
  • 🟢 11:57 Відбій тривоги в м. Харків та Харківська територіальна громада.Слідкуйте за подальшими повідомленнями.#м_Харків_та_Харківська_територіальна_громада
  • #8

можно список ребер хранить, как-то так:

City(Id, Name),
Link(Id, FromCityId, ToCityId, Distance)
 
  • 🟢 11:57 Відбій тривоги в м. Харків та Харківська територіальна громада.Слідкуйте за подальшими повідомленнями.#м_Харків_та_Харківська_територіальна_громада
  • #9
А как хранить те города которые идут от Первичного и до Конечного городов?
То есть Харьков -Песочин-Валки.....-Малая Александровка -Счастливое - Киев
 
  • 🟢 11:57 Відбій тривоги в м. Харків та Харківська територіальна громада.Слідкуйте за подальшими повідомленнями.#м_Харків_та_Харківська_територіальна_громада
  • #10
  • 🟢 11:57 Відбій тривоги в м. Харків та Харківська територіальна громада.Слідкуйте за подальшими повідомленнями.#м_Харків_та_Харківська_територіальна_громада
  • #11
А как мне просчитать тогда дистанцию как вот тут
⚠ Тільки зареєстровані користувачі бачать весь контент та не бачать рекламу.
 
  • 🟢 11:57 Відбій тривоги в м. Харків та Харківська територіальна громада.Слідкуйте за подальшими повідомленнями.#м_Харків_та_Харківська_територіальна_громада
  • #12
  • 🟢 11:57 Відбій тривоги в м. Харків та Харківська територіальна громада.Слідкуйте за подальшими повідомленнями.#м_Харків_та_Харківська_територіальна_громада
  • #13
Я понимаю что сложением Но как скрипт узнает что чтобы доехать в Киев лучше ехать через песочин и валки а не через житомир, например. Соответственно мне нужно хранить массив значений?
 
  • 🟢 11:57 Відбій тривоги в м. Харків та Харківська територіальна громада.Слідкуйте за подальшими повідомленнями.#м_Харків_та_Харківська_територіальна_громада
  • #14
хранишь обычную матрицу достижимости с весами
problem?
 
  • 🟢 11:57 Відбій тривоги в м. Харків та Харківська територіальна громада.Слідкуйте за подальшими повідомленнями.#м_Харків_та_Харківська_територіальна_громада
  • #15
Как это сделать?То есть можете показать на двух городах (Харьков - Киев) например пожалуйста
 
  • 🟢 11:57 Відбій тривоги в м. Харків та Харківська територіальна громада.Слідкуйте за подальшими повідомленнями.#м_Харків_та_Харківська_територіальна_громада
  • #16
  • 🟢 11:57 Відбій тривоги в м. Харків та Харківська територіальна громада.Слідкуйте за подальшими повідомленнями.#м_Харків_та_Харківська_територіальна_громада
  • #17
Пример можно?



Вот реализация алгоритма Дейкстры
⚠ Тільки зареєстровані користувачі бачать весь контент та не бачать рекламу.
но хоть убейте не пойму что она принимает. Вот база
⚠ Тільки зареєстровані користувачі бачать весь контент та не бачать рекламу.
Помогите связать это воедино, сколько будет стоить?. Данные у меня будет парсить парсер.
 
Останнє редагування:
  • 🟢 11:57 Відбій тривоги в м. Харків та Харківська територіальна громада.Слідкуйте за подальшими повідомленнями.#м_Харків_та_Харківська_територіальна_громада
  • #18
Что б это понять советую сделать этот алгоритм с 0, сел и написал, реализация там довольно простая. По другому в твоём случае толку не будет.
 
  • 🟢 11:57 Відбій тривоги в м. Харків та Харківська територіальна громада.Слідкуйте за подальшими повідомленнями.#м_Харків_та_Харківська_територіальна_громада
  • #19
Да я даже не знаю с чего начать)))
Первое что приходи в голову окружать города ближайшими нас.пунктами с указанием километража потом использовать алгоритм дейкстры.
Но может быть кто то это уже делал?
Или сколько будет такое стоить?
 
  • 🟢 11:57 Відбій тривоги в м. Харків та Харківська територіальна громада.Слідкуйте за подальшими повідомленнями.#м_Харків_та_Харківська_територіальна_громада
  • #20
если не получается, сделай алгоритм волны
 
Ви повинні увійти або зареєструватися, щоб відповісти.
Меню
Увійти
Реєстрація