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

[The real -=LOGAN-=]

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

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

⚠ Тільки зареєстровані користувачі бачать весь контент та не бачать рекламу.

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

 

[burning_LEGION]

запись в бд: имя_значимой_точки, координаты, другая_важная_инфа (типа вектор направления, ближайшие связи и т.д.)

а расчет расстояний на лету, получил 2 точки и погнал считать

 

[The real -=LOGAN-=]

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

 

[burning_LEGION]

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

что за матрица не представляю) видимо границы координат, по 360 градусов

 

[The real -=LOGAN-=]

Если буду по координатам тогда я потеряю просчет по автомобильным трассам. То есть как я понял должно быть так : каждый город должен быть в связях и километраж между ними?

 

[burning_LEGION]

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

 

[Klez]

Ей богу не понимаю как должно быть все организовано в БД.
Подскажите структуру таблицы подходящую для этой задачи.

мдя.. тяжелый случай, тут медицина бессильна

 

[Vlad777]

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

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

City(Id, Name),
Link(Id, FromCityId, ToCityId, Distance)

 

[The real -=LOGAN-=]

А как хранить те города которые идут от Первичного и до Конечного городов?
То есть Харьков -Песочин-Валки.....-Малая Александровка -Счастливое - Киев

 

[Klez]

А как хранить те города которые идут от Первичного и до Конечного городов?
То есть Харьков -Песочин-Валки.....-Малая Александровка -Счастливое - Киев

а зачем их хранить?

 

[The real -=LOGAN-=]

А как мне просчитать тогда дистанцию как вот тут

⚠ Тільки зареєстровані користувачі бачать весь контент та не бачать рекламу.

 

[Klez]

А как мне просчитать тогда дистанцию как вот тут

⚠ Тільки зареєстровані користувачі бачать весь контент та не бачать рекламу.

сложением

 

[The real -=LOGAN-=]

Я понимаю что сложением Но как скрипт узнает что чтобы доехать в Киев лучше ехать через песочин и валки а не через житомир, например. Соответственно мне нужно хранить массив значений?

 

[InNego]

хранишь обычную матрицу достижимости с весами
problem?

 

[The real -=LOGAN-=]

Как это сделать?То есть можете показать на двух городах (Харьков - Киев) например пожалуйста

 

[kosyak]

Как это сделать?То есть можете показать на двух городах (Харьков - Киев) например пожалуйста

ищи двунаправленный, взвешенный граф. Думаю он об этом

 

[The real -=LOGAN-=]

Пример можно?



Вот реализация алгоритма Дейкстры

⚠ Тільки зареєстровані користувачі бачать весь контент та не бачать рекламу.

но хоть убейте не пойму что она принимает. Вот база

⚠ Тільки зареєстровані користувачі бачать весь контент та не бачать рекламу.

Помогите связать это воедино, сколько будет стоить?. Данные у меня будет парсить парсер.

 

[linoman]

Что б это понять советую сделать этот алгоритм с 0, сел и написал, реализация там довольно простая. По другому в твоём случае толку не будет.

 

[The real -=LOGAN-=]

Да я даже не знаю с чего начать)))
Первое что приходи в голову окружать города ближайшими нас.пунктами с указанием километража потом использовать алгоритм дейкстры.
Но может быть кто то это уже делал?
Или сколько будет такое стоить?

 

[Klez]

если не получается, сделай алгоритм волны