Нахождение минимальных путей в разреженных графах, используя матрицу 5xN

Введение

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

Описание алгоритма

Алгоритм использует матрицу размером 5xN для хранения информации о графе и вычисления кратчайших путей. Каждая строка матрицы содержит следующую информацию:

1. Номер исходящего узла

2. Номер входящего узла

3. Длина пути между узлами

4. Сумма пути до текущего узла

5. Флаг, который меняет значения в зависимости от прохождения по разным ребрам графа

Преимущества алгоритма

1. Экономия памяти: По сравнению с базовым алгоритмом Дейкстры, который использует матрицу NxN, алгоритм использует матрицу размером 5xN, что позволяет сэкономить память, особенно при работе с большими графами.

2. Скорость вычисления: В некоторых случаях алгоритм может быть быстрее, так как он работает с меньшим количеством данных и может более эффективно обрабатывать изменения в структуре графа.

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

Пример класса на PHP

<?php

namespace GraphMatrix5xN;

class Graph
{
    private array $nodes = []; // Массив для хранения узлов и их соединений (ребер)
    private array $matrix = []; // Массив для хранения матричного представления графа

    // Добавляет узел в граф
    public function addNode(string $node): void
    {
        if (!isset($this->nodes[$node])) {
            $this->nodes[$node] = [];
        }
    }

    // Добавляет ребро между двумя узлами с указанным весом
    public function addEdge(string $from, string $to, int $weight): void
    {
        $this->nodes[$from][$to] = $weight;
        $this->nodes[$to][$from] = $weight;
    }

    // Находит кратчайший путь между начальным и конечным узлами
    public function findShortestPath(string $start, string $end): array
    {
        $visited = []; // Массив для хранения статуса посещения каждого узла
        $distances = []; // Массив для хранения текущего кратчайшего расстояния до каждого узла
        $previousNodes = []; // Массив для хранения предыдущего узла в пути для каждого узла
        $nodes = array_keys($this->nodes);

        // Инициализация массивов значениями по умолчанию
        foreach ($nodes as $node) {
            $visited[$node] = false;
            $previousNodes[$node] = null;
            $distances[$node] = INF;
        }

        $distances[$start] = 0;
        $currentNode = $start;

        // Основной цикл для обработки каждого узла
        while ($currentNode !== null) {
            $neighbors = $this->nodes[$currentNode];
            $currentDistance = $distances[$currentNode];

            // Обработка соседей текущего узла
            foreach ($neighbors as $neighbor => $weight) {
                $newDistance = $currentDistance + $weight;

                // Обновление расстояния до соседа, если найден более короткий путь
                if ($newDistance < $distances[$neighbor]) {
                    $distances[$neighbor] = $newDistance;
                    $previousNodes[$neighbor] = $currentNode;
                }
            }

            // Отмечаем текущий узел как посещенный
            $visited[$currentNode] = true;

            // Находим следующий непосещенный узел с кратчайшим расстоянием
            $currentNode = null;
            $minDistance = INF;

            foreach ($nodes as $node) {
                if (!$visited[$node] && $distances[$node] < $minDistance) {
                    $currentNode = $node;
                    $minDistance = $distances[$node];
                }
            }
        }

        // Восстанавливаем кратчайший путь из массива предыдущих узлов
        $path = [];
        $currentNode = $end;

        while ($currentNode !== null) {
$path[] = $currentNode;
$currentNode = $previousNodes[$currentNode];
}
// Разворачиваем путь и возвращаем его вместе с общим весом
    $path = array_reverse($path);
    return [
        'path' => $path,
        'totalWeight' => $distances[$end],
    ];
}
}
?>

Пример реализации

<?php 

require_once 'vendor/autoload.php';

use GraphMatrix5xN\Graph;

$graph = new Graph();

$graph->addNode('A');
$graph->addNode('B');
$graph->addNode('C');
$graph->addEdge('A', 'B', 5);
$graph->addEdge('B', 'C', 7);
$graph->addEdge('A', 'C', 10);

$result = $graph->findShortestPath('A', 'C');
print_r($result);
?>
//Array
//(
//  [path] => Array
//       (
//           [0] => A
//           [1] => C
//       )
//
//    [totalWeight] => 10
//)

Недостатки алгоритма

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

Заключение

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

Исходные коды примеров на PHP

Исходные коды на GoLang