Поиск кратчайшего пути в графе
Цена договорная
•
безналичный расчёт
для потребностей и уточнение деталей напишите свой ник в телеграмме
Имеется граф - совокупность непустого множества вершин и ребер (наборов пар вершин).
Две вершины на графе смежны, если они соединяются общим ребром.
Путь в графе представляет собой последовательность смежных вершин.
Каждое ребро имеет вес для каждого направления (из А в В один вес, из B в А другой вес). По умолчанию, за вес можно взять расстояние между вершинами графа.
Необходимо найти кратчайший путь между двумя выбранными вершинами графа, направление имеет значение.
Кратчайший путь, это набор смежных вершин с минимальной сумой весов связывающих их ребер.
Этапы:
1) REST API
Редактирование графа: создание и удаление графа, добавление вершин, удаление вершин, связывание вершин, вес ребер;
Поиск кратчайшего пути: указываем две вершины - получаем кратчайший путь;
Вся редактируемая информация должна храниться в БД.
Рекомендуемые инструменты: PHP (YII2), PostgreSQL
2) Реализовать визуализацию редактирования графа, используя вышеописанный REST API.
Фронтенд должен работать в браузере.
Допускается использовать любой Javascript фреймворк.
3) Реализовать примитивное редактирование в совместном режиме. Т.е. отображать, в реальном времени изменения графа для всех пользователей, которые открыли интерфейс управления графом.
Для реализации этого функционала можно воспользоваться стеком Node.JS - Socket.IO
Имеется граф - совокупность непустого множества вершин и ребер (наборов пар вершин).
Две вершины на графе смежны, если они соединяются общим ребром.
Путь в графе представляет собой последовательность смежных вершин.
Каждое ребро имеет вес для каждого направления (из А в В один вес, из B в А другой вес). По умолчанию, за вес можно взять расстояние между вершинами графа.
Необходимо найти кратчайший путь между двумя выбранными вершинами графа, направление имеет значение.
Кратчайший путь, это набор смежных вершин с минимальной сумой весов связывающих их ребер.
Этапы:
1) REST API
Редактирование графа: создание и удаление графа, добавление вершин, удаление вершин, связывание вершин, вес ребер;
Поиск кратчайшего пути: указываем две вершины - получаем кратчайший путь;
Вся редактируемая информация должна храниться в БД.
Рекомендуемые инструменты: PHP (YII2), PostgreSQL
2) Реализовать визуализацию редактирования графа, используя вышеописанный REST API.
Фронтенд должен работать в браузере.
Допускается использовать любой Javascript фреймворк.
3) Реализовать примитивное редактирование в совместном режиме. Т.е. отображать, в реальном времени изменения графа для всех пользователей, которые открыли интерфейс управления графом.
Для реализации этого функционала можно воспользоваться стеком Node.JS - Socket.IO
В заказе есть исполнитель
При переводе заказа из архивного в актуальный, текущий исполнитель будет снят с задачи.
Выберите тип сделки
С безопасной сделкой вы всегда сможете вернуть средства, если что-то пойдет не так. С простой сделкой вы самостоятельно договариваетесь с исполнителем об оплате и берете на себя решение конфликтов.