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

The real -=LOGAN-=

T
Статус: Офлайн
Реєстрація: 04.07.2008
Повідом.: 677
Алгоритм дейкстры

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

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

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

что за матрица не представляю) видимо границы координат, по 360 градусов
 
Если буду по координатам тогда я потеряю просчет по автомобильным трассам. То есть как я понял должно быть так : каждый город должен быть в связях и километраж между ними?
 
да, если считаешь для самолетов и точки это аэропорта, для машины точки это изменение направления дороги для каждой дороги разный коэффициент, но большинство считают их прямыми, погрешность небольшая, а экономия производительности существенная, ну кроме кольцевых дорог, но их не так много
 
The real -=LOGAN-= сказав(ла):
Я так понимаю у меня должно быть в БД город Харьков который соединяется со всеми маленькими (песочин,валки, и тд) и точно так же у Киева.
Ей богу не понимаю как должно быть все организовано в БД.
Подскажите структуру таблицы подходящую для этой задачи.
Натисніть, щоб розгорнути...

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

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



Вот реализация алгоритма Дейкстры
⚠ Тільки зареєстровані користувачі бачать весь контент та не бачать рекламу.
но хоть убейте не пойму что она принимает. Вот база
⚠ Тільки зареєстровані користувачі бачать весь контент та не бачать рекламу.
Помогите связать это воедино, сколько будет стоить?. Данные у меня будет парсить парсер.
 
Останнє редагування:
Что б это понять советую сделать этот алгоритм с 0, сел и написал, реализация там довольно простая. По другому в твоём случае толку не будет.
 
Да я даже не знаю с чего начать)))
Первое что приходи в голову окружать города ближайшими нас.пунктами с указанием километража потом использовать алгоритм дейкстры.
Но может быть кто то это уже делал?
Или сколько будет такое стоить?
 
если не получается, сделай алгоритм волны
 
Ви повинні увійти або зареєструватися, щоб відповісти.
Назад
Зверху Знизу