¿Existe un algoritmo óptimo para encontrar la ruta más corta más larga en una red?

Tengo un gran conjunto de redes lineales y me gustaría encontrar los dos extremos de cada red que están más distantes entre sí a lo largo de la red (en la imagen a continuación, sería D a K). La solución de la fuerza bruta para este problema es calcular la ruta más corta a lo largo de la red para cada par de origen, pero tengo cientos de redes con miles de extremos, por lo que calcular cada ruta posible es bastante pesado.

¿Hay una manera óptima de calcular esto sin usar la fuerza bruta? ¿Puedo excluir algunos puntos basados ​​en algunas reglas inteligentes?

EDITAR: He agregado una ilustración del camino más largo mencionado por @Alex Tereshenkov para aclarar mi pregunta. La ruta negra es el resultado del algoritmo de ruta más larga (ruta más larga sin repetir vértices). En mi caso, imagine que ingresa a la red desde cualquiera de las letras y necesita conducir a otra letra lo más rápido que pueda. ¿Qué dos letras son las más difíciles de unir?

Creo que puede estar buscando el diámetro del gráfico de su red. Hay un par de preguntas sobre stackexchange que mencionan este tema, por ejemplo:

• La complejidad temporal de encontrar el diámetro de un gráfico
• ¿Buen algoritmo para encontrar el diámetro de un gráfico (escaso)?
• ¿Qué se entiende por diámetro de una red?
• Diferencia entre el diámetro de un gráfico y la ruta más larga del gráfico

La mayoría de los algoritmos sugieren calcular primero los "caminos más cortos de todos los pares" y seleccionar el más largo de ellos, pero encontré una publicación de blog de Koushik Narayanan que sugiere un enfoque alternativo que podría ser más óptimo (no lo comprobé), que itera sobre cada vértice y encuentra su par más distante:

Podemos calcular la ruta desde un vértice V1 de modo que sea la ruta más corta entre V1 y uno de los vértices y sea más larga que la ruta más corta entre cualquier otro vértice. Ver esta publicación para un algoritmo. Luego, podemos recorrer cada vértice y encontrar el camino más largo con cada vértice como raíz. Una vez que tengamos la lista de todas las rutas más cortas más largas, podemos encontrar la que tenga el valor máximo y devolverla.

De acuerdo con la página de Wikipedia El problema del camino más largo , este problema

... es NP-hard, lo que significa que no se puede resolver en tiempo polinómico para gráficos arbitrarios a menos que P = NP. También se conocen resultados de dureza más fuertes que muestran que es difícil aproximarse. Sin embargo, tiene una solución de tiempo lineal para gráficos acíclicos dirigidos, que tiene aplicaciones importantes para encontrar la ruta crítica en los problemas de programación.

Si trabaja con (o puede representar su gráfico como DAG ), el networkxpaquete Python le permitirá calcularlo. Busca la función dag_longest_path.

A menos que me falte algo, deberá calcular la longitud entre los nodos del gráfico y ordenarlos, lo que, desafortunadamente, funcionará solo en tiempo lineal , es decir, no hay un algoritmo eficiente para esto.