Графами удобно моделировать задачи оптимизации. Для этого существует множество графовых алгоритмов, таких как Дейкстры, Крускала, Прима и многие другие. Рассматриваемый алгоритм Прима является наиболее легко реализуемым. Его смысл заключается в том, что нам необходимо каждый раз наращивать остов, прибавляя к нему наиболее оптимальное ребро, это свойство определяет принадлежность алгоритма к «жадным». Данный алгоритм подходит для решения транспортной задачи, т.к. новое присоединяемое ребро должно исходить из конечной точки предыдущего.
Перед тем, как приступить к написанию кода создадим датасет из матрицы A×B для примера. В нем будут содержаться вымышленные координаты точек для посещения и расстояния между ними, на основе которых нам необходимо составить оптимальный маршрут.
Теперь отрисуем наш граф связности или карту возможных путей проезда.
Так как для реализации будем использовать матрицу смежности, создадим ее с использованием ранее созданных Nodes и Edges.
Для приведенного ниже наглядного примера будем использовать тривиальную реализацию алгоритма Прима. Применим рассматриваемый алгоритм на графе, который хранится в виде созданной ранее матрицы смежности.
Инициализация алгоритма начинается с того, что мы присваиваем переменной dist значение 0 для точки старта и указываем значение бесконечность для всех других вершин. Теперь, используя данные из ранее созданного списка MST, последовательно визуализируем все ребра оптимального дерева.
После выполнения этого шага искомое дерево содержит две вершины, и теперь снова мы ищем оптимальное ребро, имеющее один конец в одной из двух выбранных вершин, а второй — в любой другой, но не в ранее выбранных. Повторяем этот процесс, пока все вершины не будут входить в наше оптимальное дерево. Процесс добавления ребер представлен ниже.
Теперь нам только осталось сравнить последовательность пути, выбранную алгоритмом с последовательностью, совершенной по факту.