Алгоритм Йена

В теории графов алгоритм Йена безцикловые пути с одним источником вычисляет K -кратчайшие для графа с неотрицательной стоимостью ребра . Алгоритм был опубликован Джином И. Йеном в 1971 году и использует любой алгоритм кратчайшего пути для поиска лучшего пути, а затем переходит к поиску K - 1 отклонений лучшего пути.

Алгоритм

Терминология и обозначения

Обозначения	Описание
$N$	Размер графа, т. е. количество узлов в сети.
$(i)$	The $i$-й узел графа, где $i$ варьируется от $1$ к $N$. Это означает, что $(1)$ является исходным узлом графа, а $(N)$ является стоковым узлом графа.
$d_{ij}$	Стоимость границы между $(i)$ и $(j)$, предполагая, что $(i)\neq (j)$ и $d_{ij}\geq 0$.
$A^{k}$	The $k$-й кратчайший путь из $(1)$ к $(N)$, где $k$ варьируется от $1$ к $K$. Затем $A^{k}=(1)-(2^{k})-(3^{k})-\cdots -({Q_{k}}^{k})-(N)$, где $(2^{k})$ это второй узел $k$-й кратчайший путь, $(3^{k})$ является третьим узлом $k$-й кратчайший путь и так далее.
${A^{k}}_{i}$	Путь отклонения от $A^{k-1}$ в узле $(i)$, где $i$ варьируется от $1$ к $Q_{k}$. Обратите внимание, что максимальное значение $i$ является $Q_{k}$, который является узлом непосредственно перед стоком в $k$ кратчайший путь. Это означает, что траектория отклонения не может отклоняться от заданной. $k-1$ кратчайший путь к мойке. Пути $A^{k}$ и $A^{k-1}$ идите по тому же пути до тех пор, пока $i$-й узел, тогда $(i)^{k}-(i+1)^{k}$ ребро отличается от любого пути в $A^{j}$, где $j$ варьируется от $1$ к $k-1$.
${R^{k}}_{i}$	Корневой путь ${A^{k}}_{i}$ из этого следует, что $A^{k-1}$ до тех пор, пока $i$-й узел $A^{k-1}$.
${S^{k}}_{i}$	Подъездная дорога ${A^{k}}_{i}$ это начинается с $i$-й узел ${A^{k}}_{i}$ и заканчивается у раковины.

Описание

Алгоритм можно разбить на две части: определение первого k-кратчайшего пути , $A^{1}$, а затем определение всех остальных k -кратчайших путей. Предполагается, что контейнер $A$ будет содержать k -кратчайший путь, тогда как контейнер $B$ будет содержать потенциальные k -кратчайшие пути. Чтобы определить $A^{1}$, кратчайшего пути от источника к приемнику, любой эффективный алгоритм кратчайшего пути можно использовать .

Чтобы найти $A^{k}$, где $k$ варьируется от $2$ к $K$, алгоритм предполагает, что все пути из $A^{1}$ к $A^{k-1}$ были обнаружены ранее. $k$ итерацию можно разделить на два процесса: поиск всех отклонений ${A^{k}}_{i}$ и выбираем путь минимальной длины, чтобы стать $A^{k}$. Обратите внимание, что в этой итерации $i$ варьируется от $1$ к ${Q^{k}}_{k}$.

Первый процесс можно разделить еще на три операции: выбор ${R^{k}}_{i}$, находя ${S^{k}}_{i}$, а затем добавив ${A^{k}}_{i}$ в контейнер $B$. Корневой путь, ${R^{k}}_{i}$, выбирается путем нахождения подпути в $A^{k-1}$ который следует за первым $i$ узлы $A^{j}$, где $j$ варьируется от $1$ к $k-1$. Затем, если путь найден, стоимость ребра $d_{i(i+1)}$ из $A^{j}$ установлено на бесконечность. Дальше отрог, ${S^{k}}_{i}$, находится путем вычисления кратчайшего пути от ответвления узла, узла $i$, в раковину. Удаление ранее использованных кромок из $(i)$ к $(i+1)$ гарантирует, что путь отвода отличается. ${A^{k}}_{i}={R^{k}}_{i}+{S^{k}}_{i}$, добавлен корневой путь и ответвленный путь. $B$. Затем ребра, которые были удалены, т. е. стоимость которых была установлена ​​на бесконечность, восстанавливаются до исходных значений.

Второй процесс определяет подходящий путь для $A^{k}$ найдя путь в контейнере $B$ с наименьшей стоимостью. Этот путь удален из контейнера $B$ и вставил в контейнер $A$, и алгоритм переходит к следующей итерации.

Псевдокод

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

function YenKSP(Graph, source, sink, K):
    // Determine the shortest path from the source to the sink.
    A[0] = Dijkstra(Graph, source, sink);
    // Initialize the set to store the potential kth shortest path.
    B = [];
    
    for k from 1 to K:
        // The spur node ranges from the first node to the next to last node in the previous k-shortest path.
        for i from 0 to size(A[k − 1]) − 2:
            
            // Spur node is retrieved from the previous k-shortest path, k − 1.
            spurNode = A[k-1].node(i);
            // The sequence of nodes from the source to the spur node of the previous k-shortest path.
            rootPath = A[k-1].nodes(0, i);
            
            for each path p in A:
                if rootPath == p.nodes(0, i):
                    // Remove the links that are part of the previous shortest paths which share the same root path.
                    remove p.edge(i,i + 1) from Graph;
            
            for each node rootPathNode in rootPath except spurNode:
                remove rootPathNode from Graph;
            
            // Calculate the spur path from the spur node to the sink.
            // Consider also checking if any spurPath found
            spurPath = Dijkstra(Graph, spurNode, sink);
            
            // Entire path is made up of the root path and spur path.
            totalPath = rootPath + spurPath;
            // Add the potential k-shortest path to the heap.
            if (totalPath not in B):
                B.append(totalPath);
            
            // Add back the edges and nodes that were removed from the graph.
            restore edges to Graph;
            restore nodes in rootPath to Graph;
                    
        if B is empty:
            // This handles the case of there being no spur paths, or no spur paths left.
            // This could happen if the spur paths have already been exhausted (added to A), 
            // or there are no spur paths at all - such as when both the source and sink vertices 
            // lie along a "dead end".
            break;
        // Sort the potential k-shortest paths by cost.
        B.sort();
        // Add the lowest cost path becomes the k-shortest path.
        A[k] = B[0];
        // In fact we should rather use shift since we are removing the first element
        B.pop();
    
    return A;

Пример

Yen's k-shortest path algorithm, K = 3, A to F

В примере используется алгоритм Йена K -Shortest Path для вычисления трех путей из $(C)$ к $(H)$. Алгоритм Дейкстры используется для расчета наилучшего пути из $(C)$ к $(H)$, что $(C)-(E)-(F)-(H)$ со стоимостью 5. Этот путь добавляется в контейнер $A$ и становится первым k -кратчайшим путем, $A^{1}$.

Узел $(C)$ из $A^{1}$ становится ответвленным узлом с собственным корневым путем, ${R^{2}}_{1}=(C)$. Край, $(C)-(E)$, удаляется, поскольку он совпадает с корневым путем и путем в контейнере $A$. Алгоритм Дейкстры используется для расчета ответвления. ${S^{2}}_{1}$, что $(C)-(D)-(F)-(H)$, стоимость 8. ${A^{2}}_{1}={R^{2}}_{1}+{S^{2}}_{1}=(C)-(D)-(F)-(H)$ добавляется в контейнер $B$ как потенциальный k -кратчайший путь.

Узел $(E)$ из $A^{1}$ становится отводным узлом с ${R^{2}}_{2}=(C)-(E)$. Край, $(E)-(F)$, удаляется, поскольку он совпадает с корневым путем и путем в контейнере $A$. Алгоритм Дейкстры используется для расчета ответвления. ${S^{2}}_{2}$, что $(E)-(G)-(H)$, стоимость 7. ${A^{2}}_{2}={R^{2}}_{2}+{S^{2}}_{2}=(C)-(E)-(G)-(H)$ добавляется в контейнер $B$ как потенциальный k -кратчайший путь.

Узел $(F)$ из $A^{1}$ становится ответвленным узлом с корневым путем, ${R^{2}}_{3}=(C)-(E)-(F)$. Край, $(F)-(H)$, удаляется, поскольку он совпадает с корневым путем и путем в контейнере $A$. Алгоритм Дейкстры используется для расчета ответвления. ${S^{2}}_{3}$, что $(F)-(G)-(H)$, стоимость 8. ${A^{2}}_{3}={R^{2}}_{3}+{S^{2}}_{3}=(C)-(E)-(F)-(G)-(H)$ добавляется в контейнер $B$ как потенциальный k -кратчайший путь.

Из трех путей в контейнере $B$, ${A^{2}}_{2}$ выбран, чтобы стать $A^{2}$ потому что он имеет наименьшую стоимость 7. Этот процесс продолжается до 3-го k -кратчайшего пути. Однако обратите внимание, что в рамках этой третьей итерации некоторые ответвления не существуют. И путь, который выбран, чтобы стать $A^{3}$ является $(C)-(D)-(F)-(H)$.

Функции

Пространственная сложность

Чтобы сохранить ребра графа, список кратчайших путей $A$и потенциальный список кратчайших путей $B$, $N^{2}+KN$ требуются адреса памяти. В худшем случае каждый узел графа имеет ребро к каждому другому узлу графа, таким образом $N^{2}$ адреса нужны. Только $KN$ адреса нужны для обоих списков $A$ и $B$ потому что максимум только $K$ пути будут сохранены, где возможно, чтобы каждый путь имел $N$ узлы.

Временная сложность

Временная сложность алгоритма Йена зависит от алгоритма кратчайшего пути, используемого при вычислении ответвлений, поэтому предполагается алгоритм Дейкстры. Алгоритм Дейкстры имеет худшую временную сложность: $O(N^{2})$, но с использованием кучи Фибоначчи это становится $O(M+N\log N)$, где $M$ — количество ребер в графе. Поскольку алгоритм Йена делает $Kl$ обращается к Дейкстре при вычислении ответвлений, где $l$ длина подъездных путей. На сокращенном графике ожидаемое значение $l$ является $O(\log N)$, а худший случай $N$. Временная сложность становится $O(KN(M+N\log N))$.

Улучшения

Алгоритм Йена можно улучшить, используя кучу для хранения $B$, множество потенциальных k -кратчайших путей. Использование кучи вместо списка улучшит производительность алгоритма, но не усложнит его. Один из способов немного снизить сложность — пропустить узлы, в которых отсутствуют ответвления. Этот случай возникает, когда все ответвления от ответвленного узла были использованы в предыдущем $A^{k}$. Кроме того, если контейнер $B$ имеет $K-k$ пути минимальной длины относительно путей в контейнере $A$, затем их можно извлечь и вставить в контейнер $A$ поскольку более короткие пути не будут найдены.

Модификация Лоулера

Юджин Лоулер предложил модификацию алгоритма Йена, в которой путь дубликатов не рассчитывается, в отличие от исходного алгоритма, в котором они вычисляются, а затем отбрасываются, когда обнаруживаются дубликаты. Эти дублирующиеся пути возникают в результате расчета ответвлений узлов в корне $A^{k}$. Например, $A^{k}$ отклоняется от $A^{k-1}$ в каком-то узле $(i)$. Любой подъездной путь, ${S^{k}}_{j}$ где $j=0,\ldots ,i$, которые будут рассчитаны, будут дубликатом, поскольку они уже были рассчитаны во время $k-1$ итерация. Таким образом, только ответвления для узлов, которые находились на ответвлении $A^{k-1}$ необходимо рассчитать, т.е. только ${S^{k}}_{h}$ где $h$ варьируется от $(i+1)^{k-1}$ к $(Q_{k})^{k-1}$. Чтобы выполнить эту операцию для $A^{k}$, необходима запись для идентификации узла, в котором $A^{k-1}$ ответвление от $A^{k-2}$.

См. также

• Улучшение Йена алгоритма Беллмана – Форда

Внешние ссылки

• Реализация C++ с открытым исходным кодом
• Реализация C++ с открытым исходным кодом с использованием библиотеки Boost Graph