Algorithmus für Durchmesser von graph?

Ich weiß, ich bin ein Jahr zu spät auf den thread, aber ich glaube nicht, dass diese Angaben korrekt sind. OP erwähnt in den Kommentaren, dass die Kanten nicht gewichtet; in diesem Fall, den besten Algorithmus läuft in $O(n^{\omega}) \log n$ Zeit (wobei $\omega$ ist der exponent für die matrix-Multiplikation; derzeit oben begrenzt auf $2.373$ von Virginia Williams).

Der Algorithmus nutzt folgende Eigenschaft der ungewichtete Graphen. Sei $A$ die matrix des angrenzens der graph mit einer zusätzlichen selbst-Schleife für jeden Knoten. Dann ist $(A^k)_{ij}$ ist nicht null, iff $d(i, j) \le k$. Wir können diese Tatsache nutzen, um zu finden Sie die Grafik Durchmesser von EDV $\log n$ die Werte von $A^k$.

Hier ist, wie der Algorithmus funktioniert: sei $A$ die matrix des angrenzens der graph mit einer zusätzlichen selbst-Schleife für jeden Knoten. Set $M_0 = A$. Während $M_k$ enthält mindestens eine null ist, berechne $M_{k+1} = M_{k}^2$.

Schließlich finden Sie eine matrix $M_{K}$ mit allen von null verschiedenen Einträge. Wir wissen, dass $K \le \log n$ durch die Eigenschaft oben besprochen; deshalb haben wir durchgeführt-matrix-Multiplikation nur $O(\log n)$ - mal so viel. Wir können jetzt fortfahren, indem Sie die binäre Suche zwischen $M_{K} = A^{2^K}$ und $M_{K-1} = A^{2^{K-1}}$. Set $B = M_{K-1}$ wie folgt.

Set DURCHMESSER = $2^{k-1}$. Für $i = (K-2 \dots, 0)$, führen Sie den folgenden test:

Multiplizieren $B$ durch $M_{i}$ und prüfen Sie die sich ergebenden matrix mit Nullen. Wenn wir alle Nullen sind, dann setzen $B$ um diese matrix-Produkt, und fügen Sie $2^i$ DURCHMESSER. Ansonsten, nichts tun.

Schließlich, Rückkehr DURCHMESSER.

Als ein unbedeutendes detail, ist es möglicherweise notwendig, um alle von null verschiedenen Einträge in einer matrix zu $1$ nach jeder matrix-Multiplikation durchgeführt, so dass die Werte nicht zu groß und unhandlich zu notieren, in eine kleine Menge von Zeit.

Als eci erwähnt, eine der Lösungen ist die Verwendung des Algorithmus von Floyd und Warshall. Wenn Sie den code für eine C++ - version davon gefunden werden kann hier.

Eigentlich, wenn das Diagramm sehr groß ist, werden Sie brauchen, um den Dijkstra-Algorithmus zum finden der kürzesten Entfernung. Also es hängt davon ab, wie viele Knoten die OP ' s graph.

Graph Beschreibung - ungerichtete und ungewichtete, n Knoten m Kanten
Für den Durchmesser des Graphen, müssen wir berechnen den kürzesten Weg zwischen allen Paaren von Knoten. Kürzeste Wege zwischen einem Quellknoten zu allen anderen Knoten berechnet werden kann mithilfe der BFS-Algorithmus für eine ungerichtete und ungewichtete Graphen. Time Komplexität ist O(n + m) für 1 Knoten. Hier, da müssen wir eine BFS für n Knoten, die Gesamtzeit, die Komplexität des Findens des kürzesten Weges zwischen allen Paaren von Knoten wird O(n(n + m)). Da gibt es n(n-1)/2 Paaren von Knoten, so haben wir n(n-1)/2 Werte der kürzeste Pfad zwischen den Knoten. Für den Durchmesser, die wir brauchen, um die max, diese Werte, das ist wieder O(n*n). Also die Letzte Zeit Komplexität wird:

       O(n(n + m)) + O(n*n) = O(n(2n + m)) = O(n(n + m))

Pseudocode für immer die kürzesten Wege zwischen allen Paaren von Knoten. Wir verwenden eine matrix namens Shortest_paths speichern, um die kürzesten Pfade zwischen zwei beliebigen paar von Knoten. Wir sind eine Wörterbuch-namens flag die Werte true oder false gibt an, ob die Knoten besucht wurde oder nicht. Für jede iteration des BFS, initialisieren wir das Wörterbuch, um alle falsch. Benutzen wir eine Queue Q zur Ausführung unserer BFS.
Algorithmus BFS(für alle Knoten)

Initialize a matrix named Shortest_paths[n][n] to all -1. 
    For each source vertex s
        For each vertex v
            Flag[v] = false
        Q = empty Queue
        Flag[s] = true
        enQueue(Q,s)
        Shortest_paths[s][s] = 0
        While Queue is not empty
            Do v = Dequeue(Q)
            For each w adjacent to v
                Do if flag[w] = false
                    Flag[w] = true
                    Shortest_paths[s][w] = Shortest_paths[s][v] + 1
                    enQueue(Q,w) 
    Diameter = max(Shortest_paths)
    Return Diameter