Find the diameter of a word graph
APL (Dyalog Classic), 84 80 77 76 74 66 61 bytes



{⍵⌷⍨{⍵,⍨⊃⍋(1≠a⌷⍨⊃⍵),⍪⍺⌷a}⍣d/⊃⍸a=d←⌈/512|,a←⌊.+⍨⍣≡9*⍨2⌊⍵+.≠⍉⍵}


Try it online!

input and output are character matrices

⍵+.≠⍉⍵ matrix of hamming-like distances between words

9*⍨2⌊ leave 0s and 1s intact, turn 2+ into some large number (512=29, used as "∞")

⌊.+⍨⍣≡ floyd&amp;warshall's shortest path algorithm


⌊.+ like matrix multiplication but using min (⌊) and + instead of + and × respectively
⍨ use the same matrix on the left and right
⍣≡ repeat until convergence


d←⌈/512|, length of longest (not "∞") path, assigned to d

⊃⍸a= which two nodes does it connect, let's call them i and j

{⍵,⍨⊃⍋(1≠a⌷⍨⊃⍵),⍪⍺⌷a}⍣d/ reconstruct the path


{ }⍣d/ evaluate the { } function d times. the left arg ⍺ is always i. the right arg ⍵ starts as j and gradually accumulates the internal nodes of the path
(1≠a⌷⍨⊃⍵),⍪⍺⌷a build a 2-column matrix of these two vectors:


1≠a⌷⍨⊃⍵ booleans (0 or 1) indicating which nodes are at distance 1 to the first of ⍵
⍺⌷a distances of all graph nodes to ⍺

⊃⍋ index of the lexicographically smallest row
⍵,⍨ prepend to ⍵


⍵⌷⍨ index the original words with the path