Нахождение kth-кратчайших путей?

Question

Нахождение кратчайшего пути между двумя точками на графике - это классический вопрос с множеством хороших ответов ( Алгоритм Дейкстры , Беллмана-Форда и т. Д.) Мой вопрос:является эффективным алгоритмом, который, учитывая направленный взвешенный граф, пару узлов s и t и значение k, находит k-й кратчайший путь между s и t.В случае, если есть несколько путей одинаковой длины, которые все связаны для k-го кратчайшего, алгоритм может вернуть любой из них.

Я подозреваю, что этот алгоритм, вероятно, может быть выполнен за полиномиальное время, хотя я знаю, что может быть сокращение от проблемы самого длинного пути , которое сделало бы его NP-трудным.

Кто-нибудь знает такой алгоритм или сокращение, котороепоказать что это NP-хард?

Answer 1

Вы ищете алгоритм Йены для поиска K кратчайших путей. k th кратчайший путь будет последним путем в этом наборе.

Вот реализация алгоритма Йена.

А вот оригинальная статья , описывающая ее.

Answer 2

Лучший (и в основном оптимальный) алгоритм обусловлен Эппштейном .

Answer 3

Из доступных алгоритмов K-го кратчайшего пути алгоритм Йена является самым простым для понимания.Главным образом это происходит потому, что алгоритм Йена должен сначала вычислить все кратчайшие пути K-1, прежде чем он сможет вычислить кратчайший путь K-го, поэтому его можно разбить на подзадачи.

Более того, поскольку каждая подзадача используетстандартный алгоритм кратчайшего пути (например, алгоритм Дейкстры ), это более естественное продолжение задачи 1-й кратчайший путь до проблемы Kth кратчайший путь .

Вот как это работает для поиска 3-го кратчайшего пути в графе примера с ребрами равного веса.

1-й кратчайший путь (K = 1)

Если мы ищем 1-й кратчайший путь между началом и пунктом назначения (здесь, между D и F), мы можем просто запустить алгоритм Дейкстры.Весь код для алгоритма Йена на первой итерации:

shortest_1 = Dijkstra(graph, D, F)

При наличии начального графа это дает 1-й кратчайший путь (K = 1).

2-й кратчайший путь (K = 2)

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

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

Сначала мы пытаемся удалитьребро D-E (первое ребро в shortest_1), а затем завершите кратчайший путь, введя Dijkstra(graph_1, D, F).Мы объединяем кратчайший путь, уже известный от узла D до D (который является просто самим узлом D), с новым кратчайшим путем от узла D до F.Это дает нам альтернативный путь D->F.

Затем мы пытаемся удалить ребро E-F (второе ребро в shortest_1), а затем завершить кратчайший путь, выполнив Dijkstra(graph_2, E, F).Мы объединяем кратчайший путь, уже известный от узла D до E, с новым кратчайшим путем от узла E до F.Это дает нам еще один альтернативный путь D->F.

Процедура для 2-й итерации выглядит следующим образом:

// Try without edge 1
graph_1 = remove_edge(graph, D-E)
candidate_1 = shortest_1(D, D) + Dijkstra(graph_1, D, F)

// Try without edge 2
graph_2 = remove_edge(graph, E-F)
candidate_2 = shortest_1(D, E) + Dijkstra(graph_2, E, F)

shortest_2 = pick_shortest(candidate_1, candidate_2)

В конце выбирается самый короткий из альтернативных новых путейкак 2-й кратчайший путь.

3-й кратчайший путь (K = 3)

Так же, как 2-й кратчайший путь был найден путем удаления ребер из 1-го кратчайшего пути,3-й кратчайший путь находится путем удаления ребер из 2-го кратчайшего пути.

Однако на этот раз новый нюанс заключается в том, что когда мы удаляем ребро D-A (первое ребро в shortest_2), мы также хотим удалить ребро D-E.Если мы этого не сделаем и удалим только ребро D-A, то при запуске Dijkstra на graph_3 мы снова найдем 1-й кратчайший путь (D-E-F) вместо 3-го кратчайшего пути!

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

Таким образом, общая процедура выглядит аналогично нахождению 2-го кратчайшего пути, но с нюансом, что мы также хотим удалить некоторые ребра, видимые в1-й кратчайший путь в дополнение ко 2-му кратчайшему пути.Решение принимается в зависимости от того, имеют ли shortest_1 и shortest_2 подпуть, ведущий к удаляемому краю.

// Try without edge 1
edges_3 = [D-A]
if shortest_1 and shortest_2 share subpath up to node D: 
    // True because both shortest_1 and shortest_2 have D in shortest path
    // D-E is edge in shortest_1 that is connected from D, and so it is added
    edges_3.add(D-E)

graph_3 = remove_edges(graph, edges_3)
candidate_3 = shortest_e(D, D) + Dijkstra(graph_3, D, F) // returns infinity


// Try without edge 2
edges_4 = [A-E]
if shortest_1 and shortest_2 share subpath up to node A:
    // False because there are no edges in shortest_1 that go through A
    // So no edges added

graph_4 = remove_edges(graph, edges_4)
candidate_4 = shortest_2(D, A) + Dijkstra(graph_4, A, F) // returns infinity


// Try without edge 3
edges_5 = [E-F]
if shortest_1 and shortest_2 share subpath up to node E:
    // False because shortest_1 goes through D-E while shortest_2 goes through D-A-E
    // So no edges added

graph_5 = remove_edges(graph, edges_5)
candidate_5 = shortest_2(D, E) + Dijkstra(graph_5, E, F)


shortest_3 = pick_shortest(candidate_2, candidate_3, candidate_4, candidate_5)

Обратите внимание, как при выборекратчайший путь на этот раз, мы учитываем неиспользованные кандидаты из итерации 2 (то есть candidate_2) и фактически выбираем кратчайший путь, найденный из graph_2.Таким же образом на следующей итерации (K = 4) мы обнаружим, что 4-й кратчайший путь был фактически найден в итерации K = 3.Как вы можете видеть, этот алгоритм выполняет работу заранее, поэтому, пока он находит K-й кратчайший путь, он также исследует некоторые пути за пределами K-го кратчайшего пути.Таким образом, это не самый оптимальный алгоритм для задачи K кратчайшего пути.Алгоритм Эппштейна может работать лучше, но он сложнее.

Приведенный выше подход можно обобщить, используя несколько вложенных циклов.Страница Википедии об алгоритме Йена уже дает отличный псевдокод для более общей реализации, поэтому я воздержусь от ее написания здесь.Обратите внимание, что код Википедии использует список A для хранения каждого кратчайшего пути и список B для хранения каждого пути-кандидата, и что кратчайшие пути-кандидаты сохраняются на протяжении итераций цикла.

Замечания

Из-за использования алгоритма Дейкстры алгоритм Йена не может иметь K-й кратчайший путь, который содержит цикл.Это не так заметно, когда используются невзвешенные ребра (как в примере выше), но может произойти, если добавить веса.По этой причине алгоритм Эппштейна также работает лучше, поскольку он рассматривает циклы. Этот другой ответ включает ссылку на хорошее объяснение алгоритма Эппштейна.

Answer 4

Несмотря на то, что на вопрос есть действительный принятый ответ, этот ответ решает проблему реализации путем предоставления примера рабочего кода.Найдите действительный код для k-го кратчайшего пути здесь:

// Сложность времени: O (V k (V * logV + E))

using namespace std;

typedef long long int ll;
typedef short int i16;
typedef unsigned long long int u64;
typedef unsigned int u32;
typedef unsigned short int u16;
typedef unsigned char u8;

const int N = 128;

struct edge
{
    int to,w;
    edge(){}
    edge(int a, int b)
    {
        to=a;
        w=b;
    }
};

struct el
{
    int vertex,cost;
    el(){}
    el(int a, int b)
    {
        vertex=a;
        cost=b;
    }
    bool operator<(const el &a) const
    {
        return cost>a.cost;
    }
};

priority_queue <el> pq;

vector <edge> v[N];

vector <int> dist[N];

int n,m,q;

void input()
{
    int i,a,b,c;
    for(i=0;i<N;i++)
        v[i].clear();
    for(i=1;i<=m;i++)
    {
        scanf("%d %d %d", &a, &b, &c);
        a++;
        b++;
        v[a].push_back(edge(b,c));
        v[b].push_back(edge(a,c));
    }
}

void Dijkstra(int starting_node, int ending_node)
{
    int i,current_distance;
    el curr;
    for(i=0;i<N;i++)
        dist[i].clear();
    while(!pq.empty())
        pq.pop();
    pq.push(el(starting_node,0));
    while(!pq.empty())
    {
        curr=pq.top();
        pq.pop();
        if(dist[curr.vertex].size()==0)
            dist[curr.vertex].push_back(curr.cost);
        else if(dist[curr.vertex].back()!=curr.cost)
            dist[curr.vertex].push_back(curr.cost);
        if(dist[curr.vertex].size()>2)
            continue;
        for(i=0;i<v[curr.vertex].size();i++)
        {
            if(dist[v[curr.vertex][i].to].size()==2)
                continue;
            current_distance=v[curr.vertex][i].w+curr.cost;
            pq.push(el(v[curr.vertex][i].to,current_distance));
        }
    }
    if(dist[ending_node].size()<2)
        printf("?\n");
    else
        printf("%d\n", dist[ending_node][1]);
}

void solve()
{
    int i,a,b;
    scanf("%d", &q);
    for(i=1;i<=q;i++)
    {
        scanf("%d %d", &a, &b);
        a++;
        b++;
        Dijkstra(a,b);
    }
}

int main()
{
    int i;
    for(i=1;scanf("%d %d", &n, &m)!=EOF;i++)
    {
        input();
        printf("Set #%d\n", i);
        solve();
    }
    return 0;
}