Поиск кратчайшего пути в распределённой системе

В этом задании вы реализуете алгоритм поиска кратчайшего пути от узла-инициатора до каждого узла распределённой системы и определения момента останова этого алгоритма.

Постановка задачи

В файле DijkstraProcess.kt находится описание интерфейса, который вам предстоит реализовать. Свой код на языке Kotlin пишите в файле DijkstraProcessImpl.kt.

Допустима также реализация на Java. Для этого удалите DijkstraProcessImpl.kt и вместо него напишите файл DijkstraProcessImpl.java с классом solution.DijkstraProcessImpl, который реализует интерфейс solution.DijkstraProcessи имеет публичный конструктор, принимающий ссылку на объект реализующий интерфейс solution.Environment. Шаблон для такого класса дан в файле src/solution/DijkstraProcessJavaImpl.java.

Окружение процесса

В этом задании распределённая система рассматривается как ориентированный взвешенный граф, в котором у каждого процесса v есть множество соседей N(v).

Каждому из процессов системы будет присвоен уникальный идентификатор. Через ссылку на объект Environment ваш процесс может узнать конфигурацию системы, общаться с другими процессами и сообщать об останове диффундирующего вычисления:

• env.processId — возвращается идентификатор вашего процесса.
• env.neighbours — возвращает множество процессов-соседей вашего процесса, при этом для каждого процесса-соседа указан его идентификатор и расстояние от вашего процесса до этого соседа.
• env.send(dstId, message) — посылает сообщение процессу с идентификатором dstId. При этом топология сети неполная: процесс v может послать сообщение процессу u только если u является соседом
  v, либо v является соседом u.
• env.finishExecution() — сообщает о завершении вычисления. Этот метод может быть вызван лишь один раз, после чего вычисление будет считаться завершённым.

Методы вашего класса DijkstraProcessImpl.kt будут вызываться в следующих случаях:

• onComputationStart() — сообщает данному процессу, что он должен стать инициатором в алгоритме вычисления кратчайшего пути. Гарантируется, что только один процесс будет выбран инициатором.
• onMessage(srcId, message) — вызывается при получении сообщения от другого процесса с номером srcId. Между каждой парой процессов гарантируется FIFO порядок передачи сообщений.
• distance — вызывается после завершения вычисления. Процесс должен вернуть кратчайшее расстояние от инициатора до этого процесса, или null, если не существует пути от инициатора до этого процесса.

Работа с сообщениями

Каждое отправленное сообщение должно быть сериализуемо через механизм Java Serialization. Описание класса сообщений может выглядеть, например, так:

data class MyMessage(val key: Int, val value: String) : java.io.Serializable

или на Java:

record MyMessage(int key, String value) implements java.io.Serializable {}

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

Заметьте, что метод onMessage(srcId, message) в качестве аргумента принимает не описанный вами тип сообщения, а Any (java.lang.Object). Используйте приведения типов для приведения сообщения к нужному вам типу. Например:

if (message is MyMessage) { 
    // ... работаем с типизированным message
}

или в Java:

if (message instanceof MyMessage myMessage) {
    // ... работаем с типизированным myMessage
}

Тестирование

Тестирования реализации происходит путем запуска теста DijkstraProcessTest

Из командной строки: ./gradlew build