Finden kth-kürzeste Pfade?

Finden, den kürzesten Pfad zwischen zwei Punkten in einem Graphen ist eine klassische algorithmen Frage mit vielen guten Antworten (Der Dijkstra-Algorithmus, Bellman-Ford, etc.) Meine Frage ist, ob es einen effizienten Algorithmus, der, gegeben ein gerichteter, gewichteter graph, ein paar von Knoten s und t, und ein Wert k, findet die kth-kürzeste Pfad zwischen s und t ist. Im Falle, dass es mehrere Pfade gleicher Länge, die alle binden, die für die kth-kürzeste, es ist in Ordnung für den Algorithmus zurück, einer von Ihnen.

Ich vermute, dass dieser Algorithmus kann wahrscheinlich gemacht werden, die in polynomialer Zeit, aber ich bin mir bewusst, dass es möglicherweise zu einer Reduktion von der längster Pfad problem würde, dass es NP-hart.

Kennt jemand so ein Algorithmus, oder eine Reduktion, die zeigen, dass es NP-hart?

  • springerlink.com/content/pl0054nt2d0d2u3t
  • Sie sind fast definitiv unter Bezugnahme auf die Allgemeine k-th shortest path problem, aber wenn Sie interessiert sind, in Rand-disjunkte Pfade, die Sie finden können Sie Sie mit dem Edmonds-Karp-Algorithmus: mat.uc.pt/~eqvm/OPP/KSPP/KSPP.html
  • Nur zur info: Yen-Algorithmus ist geeignet, wenn Sie nur erwägen, einfache Pfade, in der Erwägung, dass Eppstein-Algorithmus ist für den Fall, dass nicht-einfache Pfade sind erlaubt (z.B. Pfade sind erlaubt, zu überdenken, die den gleichen Knoten mehrmals). Tangential, wenn Sie wollen, dass die streng-zweite kürzesten Weg (ich weiß, dass Sie angegeben haben, die das Gegenteil), die nicht-einfache version ist in P, der einfache, ungerichtete version ist in P (Krasikov-Edel/Zhang-Nagamochi), und die einfache gerichtete version ist NP-schwer (Lalgudi-Papaefthymiou). Auch, für was es Wert ist, ich habe nicht gesehen, alle sehr gute Beschreibungen der Yen-Algorithmus, aber ich hätte gern eine!
  • Haben Sie einen Blick auf meine Antwort in diesem Beitrag.
InformationsquelleAutor templatetypedef | 2011-08-26
  1. 9

    Die besten (und im Grunde optimalen) Algorithmus ist aufgrund Eppstein.

    InformationsquelleAutor comestibles
  2. 10

    Du suchst Yen-Algorithmus für die Suche nach K kürzesten Wege. Die kth kürzeste Pfad wird dann der Letzte Weg in diesem Satz.

    Hier ist ein Umsetzung der Yen-Algorithmus.

    Und hier ist die original Papier, es zu beschreiben.

    • Sorry ich habe keine Zeit, um es zu beschreiben, und schreiben Sie es in diesem Beitrag jetzt. Aber ich kann es später tun, wenn Sie keinen Zugriff auf das Papier.
    InformationsquelleAutor tskuzzy
  3. 2

    Aus den verfügbaren Kth shortest-path-algorithmen, Yen-Algorithmus ist am einfachsten zu verstehen. Meist ist dies, weil Yen-Algorithmus benötigt zur Berechnung aller K-1 kürzeste Pfade können vor der Berechnung der Kth kürzesten Weg, so dass es gebrochen werden kann unten in sub-Probleme.

    Darüber hinaus, da jedes Teil-problem wird mit einem standard-shortest-path-Algorithmus (z.B. Der Dijkstra-Algorithmus), es ist eine Natürliche Erweiterung von der 1. shortest-path problem der Kth kürzesten Weg problem.

    Hier ist, wie es funktioniert für die Suche nach den 3 kürzesten Weg in ein Beispiel-Diagramm mit gleich-Gewicht Kanten.

    1. shortest-path (K=1)

    Wenn wir uns für die 1. kürzesten Weg zwischen einem start-und einem Zielort (hier, zwischen D und F), wir können nur das ausführen des Dijkstra-Algorithmus. Der gesamte code für die Yen-Algorithmus in der ersten iteration ist:

    shortest_1 = Dijkstra(graph, D, F)

    Gegeben, ein Start-Diagramm, das gibt die 1. shortest-path (K=1).

    Finden kth-kürzeste Pfade?

    2. shortest-path (K=2)

    Die intuition für das finden des 2. kürzesten Weg zu nehmen, der 1. kürzesten Weg, sondern "Kraft" des Dijkstra-Algorithmus auf einer anderen, etwas weniger optimale route. Die Art und Weise Yen-Algorithmus "Kräfte" der Dijkstra-Algorithmus entlang einer anderen route, indem Sie entfernen die Kanten, die Teil der 1. kürzesten Weg.

    Aber, welche von den Kanten entfernen wir um die nächste kürzeste Pfad? Wir müssen versuchen Sie jede Kante, eins nach dem anderen, und sehen, welche Kante entfernen, gibt uns die nächste kürzeste Pfad.

    Finden kth-kürzeste Pfade?

    Zuerst werden wir versuchen, Sie zu entfernen Rand D-E (die erste Kante in shortest_1), und führen Sie dann den kürzesten Weg durch laufen Dijkstra(graph_1, D, F). Wir kombinieren der kürzeste Weg bereits bekannt aus Knoten D zu D (das ist nur die Knoten D selbst), mit den neuen kürzesten Pfad von Knoten D zu F. Dies gibt uns einen alternativen Pfad D->F.

    Dann versuchen wir zu entfernen Sie das edge - E-F (die zweite Kante in shortest_1), und führen Sie dann den kürzesten Weg durch laufen Dijkstra(graph_2, E, F). Wir kombinieren der kürzeste Weg bereits bekannt aus Knoten D zu E mit der neuen kürzesten Pfad von Knoten E zu F. Dies gibt uns doch einen alternativen Weg D->F.

    Den Verfahren für die 2. iteration so Aussehen:

    //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)

    Am Ende, die kürzeste der alternativen neue Wege gewählt, als 2. kürzesten Weg.

    3. shortest-path (K=3)

    Nur als 2. kürzester Pfad gefunden wurde, durch entfernen der Kanten aus der 1. kürzesten Pfad, der 3. kürzeste Pfad gefunden wird, durch entfernen der Kanten von der 2. kürzesten Weg.

    Die neue nuance dieser Zeit, jedoch, ist, dass, wenn wir entfernen die Kante D-A (die erste Kante in shortest_2), wollen wir auch entfernen, Rand D-E. Wenn wir dies nicht tun, und entfernen Sie nur den Rand D-A dann, wenn wir laufen, Dijkstra auf graph_3 finden wir die 1. kürzeste Pfad wieder (D-E-F), statt dem 3. shortest-path!

    Für graph_4 und graph_5 wir jedoch nicht brauchen, entfernen Sie alle anderen Kanten, da diese Kanten, wenn verwendet, wird nicht geben uns die bisher kürzeste Pfade.

    Finden kth-kürzeste Pfade?

    Damit, die gesamte Prozedur ähnelt der Suche nach der 2. kürzesten Weg, aber mit der nuance, dass wir auch möchten, entfernen Sie einige Ecken gesehen, in die 1. kürzeste Pfad zusätzlich zu den 2. kürzesten Weg. Die Entscheidung ist abhängig, ob shortest_1 und shortest_2 teilen einen Unterpfad führenden bis zu der Kante, die entfernt wird.

    //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)

    Beachten Sie, wie, wenn wir wählen den kürzesten Weg zu dieser Zeit, wir berücksichtigen unbenutzten Kandidaten aus iteration 2 (d.h. candidate_2), und eigentlich ist am Ende der kürzeste Weg gefunden aus graph_2. In der gleichen Weise, auf die nächste iteration (K=4), finden wir, dass die 4. kürzesten Pfad tatsächlich fand man in der iteration K=3. Wie Sie sehen können, ist dieser Algorithmus die Arbeit im Voraus, so, während es ist das finden der Kth kürzeste Weg, es ist auch die Erkundung einige der Wege jenseits der Kth kürzesten Weg. Es ist also nicht der optimale Algorithmus für die Kth shortest path problem. Der Eppstein-Algorithmus besser machen können, aber es ist komplexer.

    Dem obigen Ansatz kann verallgemeinert werden, indem mehrere verschachtelte Schleifen. Die Wikipedia-Seite über Yen-Algorithmus gibt bereits hervorragende pseudocode für die Allgemeine Umsetzung, also werde ich es unterlassen, es zu schreiben hier. Beachten Sie, dass der Wikipedia-code verwendet eine Liste A zu halten, den jeweils kürzesten Weg, und eine Liste B zu halten jeder Kandidat Weg, und dieser Kandidat kürzeste Pfade bleiben in den loop-Iterationen.

    Bemerkungen

    Aufgrund der Verwendung des Dijkstra-Algorithmus, Yen-Algorithmus kann nicht von einem Kth kürzesten Weg, der enthält eine Schleife. Das ist nicht so bemerkbar, wenn un-gewichteten Kanten verwendet werden (wie im Beispiel oben), aber könnte auftreten, wenn die GEWICHTE Hinzugefügt werden. Aus diesem Grund, Eppstein-Algorithmus funktioniert besser als gut, da Sie der Auffassung Schleifen. Diese andere Antwort umfasst eine link auf eine gute Erklärung von Eppstein-Algorithmus.

    InformationsquelleAutor vasilyrud
  4. -1

    Obwohl, die Frage hat einen gültigen akzeptierte Antwort, diese Antwort löst das problem der Umsetzung durch die Bereitstellung einer Beispiel-code arbeiten. Finden Sie den gültigen code für die kth kürzesten Weg hier:

    //Zeit-Komplexität: O(Vk(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;
}
    InformationsquelleAutor Aditya C
Schreibe einen Kommentar