Комментарии 22
Когда Вы пишете, что алгоритм использует матрицу "5*N", а Дейкстра "N*N"- Вы что имеете в виду? Если в графе N вершин и E ребер, то Дейкстра использует вектор 1*N (текущие найденные минимальные расстояния до узлов) и "матрицу" 3*E (для каждого ребра по два числа- номера связываемых узлов, и одно число- длина пути), но эта матрица- это де факто минимальный пакет данных для хранения графа, и получается, что Дейкстра использует просто граф и один дополнительный вектор длины 1*N к нему. Ваш алгоритм использует сам граф и в худшем случае- это дополнительно матрицу 5*E, которую можно ужать до суммы графа и "лишней" матрицы" размера 1*E + 1*N (флаги прохождения ребер и найденные наилучшие расстояни до узлов). так как в связном графе E>=N-1, Дейкстра использует матрицу не больше, чем 3*E, а Вы- 5*E, и таким образом, по памяти Дейкстра на 40% эффективнее Вашего алгоритма. По скорости тоже большой вопрос- Вам и дистанции надо обновлять, и флаги, и проходите Вы по своим узлам тоже чертекак- где гаранития, что Ваш foreach не пробежит сначала по самым дальним узлам, до которых дистанция пока бесконечная, а потом вернется к старту, чего-то там локально пересчитает, и не скажет Вам, что до узла $end дистанция бесконечная?
И вот написал я это все, и думаю- "гражданин запостил улучшение Дейксты.... весна началась, что-ли?"
Прочтите пожалуйста пункт недостатки алгоритма, для большого списка задач этот алгоритм использовать эффективнее
А чем он, собственно, отличается? Вроде, как раз он и есть.
А касательно эффективности - поиск следующей вершины с минимальным весом путем перебора всех - трындец, как неэффективно :)
я прочитал :-). приведите пример хоть одной задачи, где Ваш алгоритм эффективнее Дейкстры. просто один пример.
грустное под катом
Дейкстра гарантированно сходится или к решению, или гарантированно дает отсутствие решения. Ваш алгоритм- мне кажется может никуда не сойтись вообще.
вот Вам граф из 5 узлов
1 2 100,0
1 4 1,0
4 5 1,0
5 3 1,0
3 2 1,0
минимальное расстояние 1-2 какое?
я иду по Вашему алгоритму с узла [1] и сразу же проверяю узел [2]- дистанция d[2]=100, и узел [4]- дистанция d[4]=1. [1] visited, соседи обновлены.
перехожу к узлу [2], сосед [1] визитед, а вот d[3]- пока на бесконечности, обновляю его дистанцию до d[3] = 100,0+1,0=101,0 , все, узел [2] визитед. все его соседи обновлены.
перехожу к узлу [3]. Рядом с ним [5]- обновляю его дистанцию d[5]=102, возврат в уже визитед [2] не делается. узел [3] визитед, все соседи обновлены.
перехожу к [5]- рядом с ним [4], d[4]=1, обновляю d[5] до 2,0 и обновляю дистанции до соседей узла [5], то есть, только для узла [3], d[3]=3.0.
перехожу к [4]. все соседи визитед, его дистанция- минимальна.
Все. все узлы визитед, d[2]=100.0.
А должна быть- 4.0.
В сумме- если я нашел путь с плохой дистанцией, но где-то еще есть короткий путь через три и более узлов с хорошей дистанцией- то я могу прозевать этот короткий путь, потому что обновление дистанций соседей не распространяется дальше, чем на один узел. и Ваш алгоритм превращается в тыкву. Кажется, можно и на 4х узлах это продемонстрировать, но уже лень.
Алгоритм Дейкстры имеет временную сложность O(|V|^2) для наивной реализации или O(|V| * log|V| + |E| * log|V|) с использованием приоритетной очереди. В нашем случае, это будет примерно равно O(10 000^2) = 100 000 000 или O(10 000 * log10 000 + 50 000 * log10 000) ≈ 1 653 963 для оптимизированной реализации.
Алгоритм 5xN, в свою очередь, может иметь временную сложность O(|V| * |E|), что составляет примерно O(10 000 * 5) = 50 000.
Как видно из этого примера, алгоритм 5xN может быть более эффективным с точки зрения времени выполнения, особенно при определенных условиях, например, когда количество ребер в графе ограничено. Однако стоит заметить, что эффективность алгоритма 5xN может сильно зависеть от его реализации и конкретной задачи. С помощью этого алгоритма решались реальные задачи, ошибок небыло.
А почему |E| = 5? |E| - общее количество рёбер в графе, а не среднее на вершину. Так что для случая, когда есть хотя бы по одному ребру на вершину у вас не лучше |V|^2. Ну а если граф настолько уж разрежен, то и Дейкстра с нормальной очердью будет очень быстр. В очереди же лежат достижимые вершины, а не все, поэтому он быстро переберёт все достижимые и выйдет. За то же время количество посещённых вершин, что и у вас, только выбирать наименьший вес будет много быстрее, чем линейный поиск по всем рёбрам в графе.
Если вы утверждаете, что в каких-то случаях ваш алгоритм быстрее, то показали бы бенчмарки на этих примерах и сравнили бы с какой-нибудь готовой реализацей Дейкстры.
Я искренне рад, что моя статья привлекла столько внимания и вызвала интерес у читателей. Обязательно выделю время на проведение бенчмарков с разными вариантами алгоритма, чтобы сравнить его производительность с алгоритмом Дейкстры и другими алгоритмами поиска кратчайшего пути. Возможно, в процессе тестирования я смогу определить потенциал для дальнейшей оптимизации алгоритма 5xN, что позволит его использование стать еще более эффективным в различных сценариях. Благодарю за предложение и за активное участие в обсуждении.
Заодно расскажите, почему не какой-нибудь A* и на каком таком железе вы всё это дело запускаете ваш PHP, что дийкстра оказался слишком прожорлив для него?
Сделаю статью часть 2 где выложу примеры и графики, на Github выложил коды оптимизированного Дейкстры и пример теста (benc.php), так же Вы можете посмотреть рабочий код https://phpize.online/s/YC
И почему Дейстра сделает 1 653 963 операций? Если в графе всего 5 ребёр, то это максимум 5 итераций, сотоящих из поиска минимума в очереди из не более 5 элементов и вставок в неё же. Это 5 * (log(5) + log(5)), что не более 30 базовых сравнений, а никак не миллион. Формулы же на худший случай, если случай лучше, то это не значит, что будет впустую молотить.
Да Вы правы для графе с 5 рёбрами и 5 вершинами алгоритм Дейкстры действительно будет выполнять гораздо меньше операций, чем я указал ранее. Ваш расчет операций (5 * (log(5) + log(5))) корректно отражает количество базовых сравнений для такого случая, что составляет около 30. Выше я написал, что проведу тестирование, могли бы Вы написать ссылку на алгоритм Дейкстры который максимально оптимизирован или есть готовая быстрая библиотека на php или golang?
могли бы Вы написать ссылку на алгоритм Дейкстры который максимально оптимизирован или есть готовая быстрая библиотека на php или golang?
Не совсем понимаю, вы просите ссылку на алгоритм, в тексте указываете на его не-профпригодность...
Я рад представить вам алгоритм, который разработал для решения задачи нахождения кратчайших путей в графе, когда использование алгоритма Дейкстры было неэффективно из-за ограничений по памяти.
Обязательно выделю время на проведение бенчмарков с разными вариантами алгоритма, чтобы сравнить его производительность с алгоритмом Дейкстры и другими алгоритмами поиска кратчайшего пути.
Я просил ссылку на алгоритм или готовый код для того чтобы сравнить алгоритмы на производительность, а так же код размещу на Github с настройками и генератором случайных графов для заполнения матриц.
облегчу задачу: что сделает Ваш алгоритм вот с такими вводными:
<?php
require_once 'vendor/autoload.php';
use GraphMatrix5xN\Graph;
$graph = new Graph();
$graph->addNode('1');
$graph->addNode('2');
$graph->addNode('3');
$graph->addNode('4');
$graph->addNode('5');
$graph->addEdge('1', '2', 100);
$graph->addEdge('1', '4', 1);
$graph->addEdge('4', '5', 1);
$graph->addEdge('5', '3', 1);
$graph->addEdge('3', '2', 1);
$result = $graph->findShortestPath('1', '2');
print_r($result);
?>https://www.onlinegdb.com/online_php_interpreter Ваш код запустить не может. жалуется на PHP Parse error: syntax error, unexpected 'array' (T_ARRAY), expecting function (T_FUNCTION) or const (T_CONST) in /home/main.php on line 7
Спасибо за интерес к этому алгоритму, я еще раз все проверю и обновлю на git если найдутся ошибки
Ааа, я сонный балбес! В Вашем графе кратчайшее расстояние между A и С- это само ребро АС с длиной 10. А Ваш алгоритм выдал 12. крайне эффективно запутался в трех вершинах, я в восхищении.
У них очень старая версия РНР. Вот рабочий вариант https://phpize.online/s/zC
Как говорится
Где пруфы, Джонни
Где бенчмарки? Где сравнительная имплементация Дийкстры? Где нагрузочные тесты хотя бы с парой сотен тысяч нод?
С алгоритмом Флойда-Уоршелла какие отличия?
Алгоритм Флойда-Уоршелла находит кратчайшие пути между всеми парами вершин во взвешенном графе, имеет временную сложность O(|V|^3) и работает с отрицательными весами рёбер (но не с отрицательными циклами). Алгоритм 5xN находит кратчайший путь между двумя вершинами, имеет временную сложность O(|V| * |E|) и не учитывает отрицательные веса рёбер и циклы. Выбор алгоритма зависит от задачи и структуры графа.
Экономия памяти: По сравнению с базовым алгоритмом Дейкстры, который использует матрицу NxN, алгоритм использует матрицу размером 5xN, что позволяет сэкономить память, особенно при работе с большими графами.
Может быть, я чего-то не понимаю, но для хранения графа в алгоритме Дейкстры достаточно иметь vector<vector<int>> graph (vector = динамический массив), представляющий собой список смежности. По затратам на память это O(|E|) с константой около 2. Как Вы собираетесь хранить всю эту информацию за О(N) в предложенной матрице? Полагаю, подразумевается асимптотика О(|E|), но в таком случае константа уже 5...
Нахождение минимальных путей в разреженных графах, используя матрицу 5xN