Модификация алгоритма Дейкстры для весов ребер, взятых из диапазона

Предположим, у меня есть ориентированный граф с весами ребер, взятыми из диапазона где - константа. Если я пытаюсь найти кратчайший путь, используя алгоритм Дейкстры , как я могу изменить алгоритм / структуру данных и повысить сложность времени до ?K O ( | V | + | E |$[1,\dots, K]$$K$$O(|V|+|E|)$

Если веса ребер являются целыми числами в , вы можете реализовать Dijkstra для выполнения за , следуя предложению @ rrenaud. Вот более явное объяснение.O ( K | V | + | E |$\{0,1,\ldots,K\}$$O(K|V|+|E|)$

В любое время (конечные) ключи в очереди с приоритетами находятся в некотором диапазоне , где - это значение последнего ключа, удаленного из очереди с приоритетами. (Каждый ключ по крайней мере , потому что последовательность ключей, удаленных алгоритмом Дейкстры, неубывающая, и каждый ключ не более , потому что каждый ключ имеет значение для некоторого ребро где - расстояние от источника до некоторой вершины , которая уже удалена, поэтому )D D D + K d [ u ] + w t ( u , w ) ( u , w ) d [ u ] u d [ u ] ≤ $\{D,D+1,\ldots,D+K\}$$D$$D$$D+K$$d[u] + wt(u,w)$$(u,w)$$d[u]$$u$$d[u]\le D$

По этой вы можете реализовать очередь с приоритетом с помощью кругового массива размера , в каждой ячейке которого содержится сегмент. Сохраните каждую вершину с ключом в ячейке в ячейке где . Отслеживайте . Выполните операции следующим образом:K + 1 k A [ h ( k ) $A[0..K]$$K+1$$k$$A[h(k)]$$h(k)=k \bmod (K+1)$$D$

• удалить-мин : В то время как пуст, приращение . Затем удалите и верните вершину из .$A[h(D)]$$D$$A[h(D)]$

• вставить с ключом : добавить вершину в корзину .A [ h ( k ) $k$$A[h(k)]$

• клавиша уменьшения к : переместите вершину из в .k ′ A [ h ( k ) ] A [ h ( k ′ ) $k$$k'$$A[h(k)]$$A[h(k')]$

Вставка и уменьшение ключа являются операциями с постоянным временем, поэтому общее время, потраченное на эти операции, будет . Общее время , затраченное на Delete-мин будет плюс конечное значение . Конечным значением является максимальное (конечное) расстояние от источника до любой вершины (потому что delete-min, который занимает итераций, увеличивает на ). Максимальное расстояние не более потому что каждый путь имеет не более ребер. Таким образом, общее время, проведенное алгоритмом, составляет .$O(|V|+|E|)$$O(|V|)$$D$$D$$i$$D$$i$$K(|V|-1)$$|V|-1$$O(K|V|+|E|)$

Здесь я предполагаю, что является целым числом, а веса ребер являются целыми. В противном случае он ничего вам не купит, вы всегда можете перемасштабировать веса так, чтобы минимальное ребро стоило а максимальное стоило , поэтому проблема идентична стандартной задаче кратчайшего пути.$K$$1$$K$

Алгоритм / эскиз доказательства: Реализуйте очередь приоритетов таким сумасшедшим способом как массивсписки с ключом по стоимости и иным образом используют стандартный алгоритм Дейкстры. Держите счетчик, который отслеживает стоимость минимального элемента в куче. Разрешите вызов очереди после удаления элементов с помощью линейного сканирования . Да, это звучит безумно, но постоянная позволяет обманывать и обманывать вашу алгоритмическую интуицию против линейного сканирования. Вам нужно только отсканировать с маркера последней минуты, потому что алгоритм Disjkstra хорош для реализации вашей очереди. К тому времени, когда он запрашивает очередь, элементы, вставленные в очередь, всегда больше или равны предыдущему минимуму. Самый длинный кратчайший путь имеет длинуK K × | V | K × | V | = O ( | V |$K\times |V|$$K$$K\times |V|$Таким образом, ваша амортизированная стоимость сканирования составляет если K постоянно.$K\times |V| = O(|V|)$

Вы можете использовать топологическую сортировку, чтобы найти решение, затем позвольте источнику иметь степень 0, затем идти от каждого ребра от источника, если другая вершина имеет степень 0, затем поместите ее в очередь и продолжайте делать это. в этом случае (без цикла внутри графа) он может достичь V + E, поскольку он прошел бы через каждую вершину и ребра один и только один раз.