Encuentra el ciclo de menor longitud en un gráfico dirigido con pesos positivos

Me hicieron esta pregunta en una entrevista, pero no pude encontrar una solución decente. Entonces, les dije el enfoque ingenuo de encontrar todos los ciclos y luego elegir el ciclo con la menor longitud.

Tengo curiosidad por saber cuál es una solución eficiente para este problema.

Puede modificar fácilmente el algoritmo de Floyd-Warshall . (Si no está familiarizado con la teoría de grafos, le sugiero que la revise, por ejemplo, obtener una copia de Introducción a los algoritmos ).

Tradicionalmente, inicia la path[i][i] = 0 para cada i . Pero en su lugar puede comenzar desde la path[i][i] = INFINITY . No afectará al algoritmo en sí, ya que esos ceros no se usaron en el cálculo de todos modos (ya que la ruta de path[i][j] nunca cambiará para k == i o k == j ).

Al final, el path[i][i] es la longitud que recorre el ciclo más corto i . En consecuencia, necesita encontrar min(path[i][i]) para todo i . Y si quieres un ciclo en sí mismo (no solo su longitud), puedes hacerlo tal como se hace normalmente con rutas normales: memorizando k durante la ejecución del algoritmo.

Además, también puedes usar el algoritmo de Dijkstra para encontrar el ciclo más corto que pasa por un nodo dado. Si ejecuta este Dijkstra modificado para cada nodo, obtendrá el mismo resultado que con Floyd-Warshall. Y dado que cada Dijkstra es O(n^2) , obtendrá la misma complejidad general O(n^3) .

El pseudo código es una modificación simple del algoritmo de Dijkstra.

 for all u in V: for all v in V: path[u][v] = infinity for all s in V: path[s][s] = 0 H = makequeue (V) .. using pathvalues in path[s] array as keys while H is not empty: u = deletemin(H) for all edges (u,v) in E: if path[s][v] > path[s][u] + l(u, v) or path[s][s] == 0: path[s][v] = path[s][u] + l(u,v) decreaseKey(H, v) lengthMinCycle = INT_MAX for all v in V: if path[v][v] < lengthMinCycle & path[v][v] != 0 : lengthMinCycle = path[v][v] if lengthMinCycle == INT_MAX: print(“The graph is acyclic.”) else: print(“Length of minimum cycle is ”, lengthMinCycle) 

Complejidad del tiempo: O (| V | ^ 3)

  • Realizar DFS
  • Durante DFS mantenga la pista del tipo de borde
  • El tipo de bordes es Tree Edge , Back Edge , Down Edge y Parent Edge
  • Back Edge un seguimiento cuando obtenga un Back Edge y tenga otro contador para obtener la longitud.

Ver Algorithms in C++ Part5 - Robert Sedgwick para más detalles

Lo que tendrá que hacer es asignar otro peso a cada nodo que siempre es 1. Ahora ejecute cualquier algoritmo de camino más corto desde un nodo al mismo nodo usando estos pesos. Pero al considerar las rutas intermedias, tendrá que ignorar las rutas cuyos pesos reales son negativos.

También podemos usar el algoritmo de sucursal y destino para el problema del vendedor viajero, ya que su pregunta coincide con el TSP. http://lcm.csa.iisc.ernet.in/dsa/node187.html

A continuación se muestra una modificación simple del algoritmo de Floyd – Warshell.

  V = 4
 INF = 999999 

def minimumCycleLength (gráfico):
dist = [[0] * V para i en rango (V)]
para mí en el rango (V):
para j en el rango (V):
dist [i] [j] = gráfico [i] [j];
para k en el rango (V):
para mí en el rango (V):
para j en el rango (V):
dist [i] [j] = min (dist [i] [j], dist [i] [k] + dist [k] [j])
longitud = INF
para mí en el rango (V):
para j en el rango (V):
longitud = min (longitud, dist [i] [j])
longitud de retorno

graph = [ [INF, 1, 1,INF], [INF, INF, 1,INF], [1, INF, INF, 1], [INF, INF, INF, 1] ] length = minimumCycleLength(graph) print length