1.Эмпирическая временная сложность общего алгоритма Дейкстры(arXiv)
Автор:Петр Юркевич, Эдита Бернацкая, Ежи Домжал, Роберт Вуйчик
Аннотация: Универсальный алгоритм Дейкстры — это новый алгоритм поиска оптимального кратчайшего пути как в сетях мультиплексирования с разделением по длине волны (WDM), так и в эластичных оптических сетях (EON), который, как утверждается, значительно превосходит известные алгоритмы. Из-за своей новизны он не был независимо реализован и проверен. Его временная сложность также остается неизвестной. В этой статье мы проводим анализ времени выполнения и показываем, что время выполнения Generic Dijkstra растет квадратично с количеством вершин графа и логарифмически с количеством реберных единиц. Мы также обнаруживаем, что время работы общего алгоритма Дейкстры в функции использования сети не является монотонным, поскольку пиковое время работы составляет примерно 0,25 использования сети. Кроме того, мы предоставляем независимую реализацию Generic Dijkstra с открытым исходным кодом на языке Python. Мы подтверждаем правильность алгоритма и его превосходную производительность. По сравнению с алгоритмом Filtered Graphs алгоритм Generic Dijkstra примерно в 2,3 раза быстрее в сетях с количеством узлов от 25 до 500, а в 90% вызовов его вычисление занимает меньше времени.
2.Расширенный алгоритм Дейкстры и алгоритм Мура-Беллмана-Форда(arXiv)
Автор:Конг-Диан Ченг
Аннотация: изучите общую задачу поиска кратчайшего пути с одним источником. Во-первых, определите функцию пути на наборе некоторого пути с одним и тем же источником на графе и разработайте своего рода общую задачу кратчайшего пути с одним источником (GSSSP) для определенной функции пути. Во-вторых, следуя соответственно подходам известного алгоритма Дейкстры и алгоритма Мура-Беллмана-Форда, разработать расширенный алгоритм Дейкстры (EDA) и расширенный алгоритм Мура-Беллмана-Форда (EMBFA) для решения проблемы GSSSP при определенных заданных условиях. В-третьих, ввести несколько понятий, таких как сохранение порядка в последней дороге (OPLR) функции пути и так далее. И в предположении, что значение связанной функции пути для любого пути может быть получено за время M(n), докажите соответственно алгоритм EDA, решающий задачу GSSSP за время O(n2)M(n), и алгоритм EMBFA, решающий задачу GSSSP за время O(mn)M(n). Наконец, на нескольких примерах показаны некоторые приложения разработанных алгоритмов. То, что мы сделали, может улучшить как исследователей, так и приложения теории кратчайшего пути.
3. Модифицированный алгоритм Дейкстры с применением иерархии изобретений к коническому графу(arXiv)
Автор:Угочи А. Окенгву, Енох О. Нвачукву, Эммануэль Н. Осеги
Аннотация:предложена модифицированная версия алгоритма Дейкстры, использующая изобретательскую иерархию сжатия. Алгоритм рассматривает ориентированный ациклический граф с конической или полукруглой структурой, для которого пара ребер выбирается итеративно из нескольких источников. Алгоритм получает минимальные пути, используя процесс сравнения. Процесс сравнения следует процедуре математического построения, которая учитывает прямую и обратную проверку, так что выбираются только пути с минимальной длиной. Кроме того, алгоритм автоматически изобретает новый путь, вычисляя абсолютную разницу ребер для минимальной пары ребер и ее последующего соседа за время O (n). Изобретенный путь приближается к скрытому пути с использованием критерия пригодности. Предлагаемый алгоритм расширяет проблему множественных источников и множественных назначений, включая те пути, для которых перенаправление интеллектуального анализа пути от множества источников к множеству назначений является минимальным. Алгоритм был применен к системе поиска путей в больницах, и результаты оказались вполне удовлетворительными.
