Algorithme pour le diamètre du graphe?

Je sais que je suis un retard d'un an sur le fil, mais je ne crois pas qu'aucun de ces réponses sont correctes. OP mentionné dans les commentaires que les bords ne sont pas pondérées; dans ce cas, le meilleur algorithme s'exécute en $O(n^{\omega}) \log n$ l'heure (où $\omega$ est l'exposant de la multiplication de matrice; actuellement des limites supérieures à $2.373$ par Virginia Williams).

L'algorithme exploite la propriété suivante des graphes non pondérés. Laissez $A$ être la matrice d'adjacence du graphe avec un ajout d'un auto-boucle pour chaque nœud. Alors $(A^k)_{ij}$ est non nul ssi $d(i, j) \le k$. Nous pouvons utiliser ce fait pour trouver le graphique de diamètre par le calcul de $\log n$ valeurs de $A^k$.

Voici comment fonctionne l'algorithme: laissez $A$ être la matrice d'adjacence du graphe avec un ajout d'un auto boucle pour chaque nœud. Set $M_0 = A$. Alors que $M_k$ contient au moins un zéro, calculer $M_{k+1} = M_{k}^2$.

Par la suite, vous trouverez une matrice de $M_{K}$ avec toutes les entrées non nulles. Nous savons que $K \le \log n$ par la propriété indiqué ci-dessus; par conséquent, nous avons effectué une multiplication de matrice de seulement $O(\log n)$ fois jusqu'à présent. Nous pouvons maintenant continuer en binaire de recherche entre $M_{K} = A^{2^K}$ et $M_{K-1} = A^{2^{K-1}}$. Ensemble $B = M_{K-1}$ comme suit.

Set DIAMÈTRE = $2^{k-1}$. Pour $i = (K-2 \dots 0)$, effectuez le test suivant:

Multiplier $B$ de $M_{i}$ et contrôler la matrice de zéros. Si nous trouvons des zéros, puis définissez $B$ à cette matrice de produit, et d'ajouter $2^i$ de DIAMÈTRE. Sinon, ne rien faire.

Enfin, le retour de DIAMÈTRE.

Comme un mineur de détail d'implémentation, il pourrait être nécessaire de fixer toutes les entrées non nulles de la matrice de $1$ après chaque matrice de la multiplication est effectuée, de sorte que les valeurs ne soit pas trop grand et trop lourd à écrire dans un petit laps de temps.

OriginalL'auteur GMB

Comme ice mentionné, l'une des solutions est d'utiliser la Floyd-Warshall algorithme. Si vous avez besoin du code pour cela, une version C++ de il peut être trouvé ici.

OriginalL'auteur nbanic

En fait, si le graphe est extrêmement grande, vous aurez besoin d'utiliser l'algorithme de Dijkstra pour trouver la distance la plus courte. Donc ça dépend du nombre de nœuds de l'OP graphique.

OriginalL'auteur hbranum

Graphique de la description pure et brute, n nœuds, m bords
Pour le diamètre du graphe, nous avons besoin de calculer le chemin le plus court entre toutes les paires de nœuds. Plus courts chemins entre un nœud source vers tous les autres nœuds peuvent être calculés en utilisant l'algorithme BFS pour un non-orienté et non pondérées graphique. Complexité temporelle est O(n + m) pour 1 nœud. Ici, puisque nous avons besoin de faire un BFS pour n nœuds, le temps total de la complexité de trouver le chemin le plus court entre toutes les paires de nœuds devient O(n(n + m)). Puisqu'il y a n(n-1)/2 paires de nœuds, nous avons donc n(n-1)/2 valeurs du chemin le plus court entre tous les nœuds. Pour le diamètre, nous avons besoin de tirer le maximum de ces valeurs, ce qui est nouveau en O(n*n). Donc la dernière fois de la complexité devient:

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

Pseudo-code pour obtenir les plus courts chemins entre toutes les paires de nœuds. Nous sommes à l'aide d'une matrice nommée Shortest_paths pour stocker les chemins les plus courts entre chaque paire de nœuds. Nous sommes à l'aide d'un dictionnaire nommé drapeau qui a des valeurs vrai ou faux qui indique si le sommet a été visité ou non. Pour chaque itération de la BFS, nous initialisons ce dictionnaire à tout faux. Nous utilisons une File d'attente Q pour effectuer notre BFS.
L'algorithme BFS(pour tous les nœuds)

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

OriginalL'auteur s.dutta