Längste Wege in Graphen

Da die letzten 2 Tage,ich bin versuchen zu finden etwas Logik für die Berechnung der längste Pfad im Graphen.Ich weiß, ich kann es leicht finden, für DAGs und im Allgemeinen ist es polynomialzeit-Algorithmus.Die formal,die ich umsetzen will Heuristik zur Berechnung längster Pfad,ausserdem,wenn die Wahrscheinlichkeit p ist gegeben mit dem eine Kante vorhanden ist, in der Grafik,wie können wir das problem lösen..Hilfe...

  • beste Weg, dies zu tun ist, backtracking, in der Tat, sollten Sie besuchen alle möglichen Weg zu finden Ihre Antwort im schlimmsten Fall.
InformationsquelleAutor username_4567 | 2011-11-08
  1. 2

    Berechnung der längste Pfad nicht getan werden kann in polynomieller Zeit soweit ich weiß. Folgende java-Implementierung der längste Pfad-Algorithmus findet den längsten Pfad von a positiv gewichteten Graphen für eine gegebene Quell -, aber es dauert exponentielle Zeit in seinen schlimmsten Fall.

    public class LongestPath {
static int times;
public double initLongestPath(ArrayList<Vertex> V,Vertex source){
    for(Vertex u:V){
        u.setVisited(false);
    }
    return getLongestPath(source);
}
public double getLongestPath(Vertex v){
    ++times;
    System.out.println(times);
    double w,dist,max=0;
    v.setVisited(true);
    for(Edge e:v.getOutGoingEdges()){
        if(!e.getToNode().isVisited()){
            dist=e.getWeight()+getLongestPath(e.getToNode());
            if(dist>max)
                max=dist;
        }
    }

    v.setVisited(false);    
    return max;
}

    }

    • Können Sie einige Optimierungen, bevor Sie dies ausführen. Für jeden Knoten überprüfen, ob es hat nur zwei verbindungen. Wenn es funktioniert, dann entfernen Sie die Knoten, erstellen eine Kante zwischen den Knoten verbunden war, gleich der Summe der Pfade, die eine Verbindung zu diesem Knoten. Sie können auch entfernen Sie einige Knoten mit nur einer Verbindung (durch hinzufügen der Kosten zu bekommen, um Sie auf den Knoten, mit dem Sie verbunden sind). Beachten Sie, dass wenn Sie das tun, können Sie zählen nur bis zwei, je nachdem, wo Sie beginnen/beenden
    InformationsquelleAutor Maddy
  2. 1

    Dijkstra kann nicht verwendet werden, die auf Graphen mit negativen gewichten - Wiki-Artikel auf Dijkstra

    Dijkstra-Algorithmus, konzipiert vom niederländischen Informatiker Edsger Dijkstra 1956, erschienen 1959,Eins ist ein graph search-Algorithmus löst das single-source-shortest path problem für einen Graphen mit nicht-negative Rand Pfad Kosten ...

    So dass Sie nicht negieren alle kantengewichte und die Nutzung Dijkstra, was Sie tun können, ist zu negieren alle kantengewichte und die Nutzung Bellman-Ford-Algorithmus - Wiki-Artikel über Bellman-Ford

    Bellman–Ford-Algorithmus ist ein Algorithmus, der berechnet kürzeste Pfade von einem single-source-vertex zu allen anderen Knoten in einem gewichteten digraph.Eins Es ist langsamer als Dijkstra ' s Algorithmus für das gleiche problem, aber vielseitiger, als es ist in der Lage Umgang mit Graphen, in denen einige der kantengewichte sind negative zahlen

    EDIT: Der kürzeste Weg (mit den meisten negativen Wert) ist dann der längste Pfad im ursprünglichen Graphen.

    HINWEIS: wenn Sie positive Zyklen in Ihrem Graphen haben, werden Sie nicht finden eine Lösung, da der längste Pfad existiert nicht in solch ein Diagramm.

    InformationsquelleAutor Vlad
  3. -2

    Konnte man immer nur mit einem Breite-zuerst-Suche (BFS) und, Wann immer Sie hinzufügen eine Kante des Graphen, die Sie haben, kostete es, als das additive inverse (multiplizieren Sie es -1 sein). Auf diese Weise finden Sie den "kürzesten Weg" mit den längsten Kanten. Denn Sie tun eine Skalare transformieren, du bist nicht verlieren die Möglichkeit, um innerhalb der Gruppe (die Sie verlieren, wenn Sie die multiplikativen inversen).

    • Also P+NP? zuerst zeigen Sie Ihren Beweis entscheiden Sie dann, so schnell, kürzeste Pfad wie du sagtest, ist für Graphen mit nicht-negativen Zyklen, siehe wiki ...
    • Vorausgesetzt, es gibt nur positive GEWICHTE, BFS wird gut funktionieren. Seine Erklärung angegeben war, dass es eine 'Wahrscheinlichkeit', dass einige Kanten auftreten würde, und obwohl es streng ist keine vernünftige Annahme zu machen, dass es nur positive Kanten), es ist ein einfacher Fall von split: erlauben Sie negative Zyklen -> NP-vollständig ist, oder verbieten Sie -> verwenden, geändert (shortest path algorithmn | graph).
    • Aber Ihre Annahme in zu vielen Fällen macht negative Zyklen, so dass Ihre aktuelle Herangehensweise nicht machen einen Sinn, und der graph mit negativen Zyklus, die keinen Sinn in normalen Situationen.
    • Aber ich denke, statt des BFS, die ich verwenden kann DFS..ich werde führen Sie DFS auf jedem Knoten,auf mindestens einem Knoten DFS besuchen, um alle Scheitelpunkte..das werde längste Pfad im Graphen richtig?Aber in diesem Ansatz bekomme ich nicht, wo kann ich die Wahrscheinlichkeit verwenden..??
    InformationsquelleAutor Noxville
  4. -3

    Invertieren die GEWICHTE der Pfade und führen Sie ein shortest-path-Algorithmus. Die niedrigste Zahl, die Sie erhalten (meist negativ) ist der längste Pfad.

    • Sie sind richtig,aber probaility mit dem edge vorhanden ist in der Grafik ist auch gegeben...also, wie kann ich die Wahrscheinlichkeit berechnen?
    • Ein shortest-path-Algorithmus will paar Ecken und Kanten bei niedrigem Gewicht. Einen längsten Pfad-Algorithmus will die langen Kanten mit geringem Gewicht. Einen kürzesten Pfad alg wird nicht helfen, Sie finden einen längsten Pfad.
    • Wenn ich jeden Rand negativ und ich laufen shortest-path-Algorithmus,es kann mir Ergebnisse, die ich will(weil minimzing positiven Wert ist die gleiche wie die Maximierung negativer Wert)...aber wie wird Sie p-"Wahrscheinlichkeit, mit der Kante ist vorhanden, im Diagramm" im Algorithmus.
    • -1 kürzeste Weg ist für Graphen mit nicht-negativen Zyklus (in P).
    InformationsquelleAutor Mike K.
Schreibe einen Kommentar