¿Existe un algoritmo óptimo para encontrar el camino más corto en una red?

Question

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

¿Existe una forma óptima de calcular esto sin utilizar la fuerza bruta? ¿Puedo excluir algunos puntos basándome en algunas reglas inteligentes?

EDIT: He añadido una ilustración del camino más largo mencionado por @Alex Tereshenkov para aclarar mi pregunta. El camino negro es el resultado del algoritmo del camino más largo (camino más largo sin repetir ningún vértice). En mi caso, imagina que entras en la red desde cualquiera de las letras y tienes que conducir hasta otra letra lo más rápido que puedas. ¿Qué dos letras son las más difíciles de unir?

Answer 1

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

• La complejidad temporal de encontrar el diámetro de un grafo
• ¿Un buen algoritmo para encontrar el diámetro de un grafo (disperso)?
• ¿Qué se entiende por diámetro de una red?
• Diferencia entre el diámetro de un grafo y el camino más largo del grafo

La mayoría de los algoritmos sugieren que se calculen primero los "caminos más cortos de todos los pares" y se seleccione el más largo de ellos, pero he encontrado una entrada en el blog de Koushik Narayanan que sugiere un enfoque alternativo que podría ser más óptimo (no lo he comprobado), que itera sobre cada vértice y encuentra su par más distante:

Podemos calcular el camino desde un vértice V1 tal que sea el camino más corto entre V1 y uno de los vértices y sea más largo que el camino más corto entre cualquier otro vértice. Véase este puesto para un algoritmo. Entonces, podemos iterar por cada vértice y encontrar el camino más largo con cada vértice como raíz. Una vez que tenemos la lista de todos los caminos más cortos, podemos encontrar el que tiene el valor máximo y devolverlo.

Answer 2

Según la página de Wikipedia Problema del camino más largo Este problema

... es NP-duro, lo que significa que no puede resolverse en tiempo polinómico para grafos arbitrarios a menos que P = NP. También se conocen resultados de mayor dureza conocidos que muestran que es difícil de aproximar. Sin embargo, tiene una solución de tiempo lineal para grafos acíclicos dirigidos, que tiene importantes aplicaciones en la búsqueda del camino crítico en problemas de programación.

Si trabaja con (o puede representar su gráfico como DAG ), entonces networkx El paquete Python te permitirá calcularlo. Busque la función dag_longest_path .

A menos que me esté perdiendo algo, tendrá que calcular la longitud entre los nodos del gráfico y ordenarlos, lo que, por desgracia, sólo funcionará en tiempo lineal Es decir, no hay eficiente algoritmo para esto.