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=2⁹, used as "∞")

⌊.+⍨⍣≡ floyd&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

Jelly, 20 bytes

ŒPŒ!€ẎnƝ§ỊẠƲƇ.ịⱮḢƙƊṪ

Try it online!

Python 3, 225 bytes

from itertools import*
def f(a):b=[((p[0],p[-1]),(len(p),p))for i in range(len(a))for p in permutations(a,i+1)if all(sum(q!=r for q,r in zip(*x))<2for x in zip(p,p[1:]))];return max(min(r for q,r in b if x==q)for x,y in b)[1]

Try it online!

Basically, take all possible paths, only keep the ones that are valid, then go through each start-end combination, find the minimum path distance, and find the maximum of that.