Поиск кратчайшего пути в графе

Цена договорная • безналичный расчёт
08 ноября 2018, 18:21 • 6 откликов • 114 просмотров
для потребностей и уточнение деталей напишите свой ник в телеграмме

Имеется граф - совокупность непустого множества вершин и ребер (наборов пар вершин).
Две вершины на графе смежны, если они соединяются общим ребром.
Путь в графе представляет собой последовательность смежных вершин.
Каждое ребро имеет вес для каждого направления (из А в В один вес, из B в А другой вес). По умолчанию, за вес можно взять расстояние между вершинами графа.

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

Этапы:

1) REST API
Редактирование графа: создание и удаление графа, добавление вершин, удаление вершин, связывание вершин, вес ребер;
Поиск кратчайшего пути: указываем две вершины - получаем кратчайший путь;
Вся редактируемая информация должна храниться в БД.
Рекомендуемые инструменты: PHP (YII2), PostgreSQL

2) Реализовать визуализацию редактирования графа, используя вышеописанный REST API.
Фронтенд должен работать в браузере.
Допускается использовать любой Javascript фреймворк.

3) Реализовать примитивное редактирование в совместном режиме. Т.е. отображать, в реальном времени изменения графа для всех пользователей, которые открыли интерфейс управления графом.
Для реализации этого функционала можно воспользоваться стеком Node.JS - Socket.IO