graph - ¿Cómo encontrar el ciclo dirigido mínimo (peso mínimo total)?

Question

Aquí se presenta una especial:

Sea G un grafo dirigido ponderado con n vértices y m bordes, donde todos los bordes tienen un peso positivo. Un ciclo dirigido es un camino dirigido que comienza y termina en el mismo vértice y contiene al menos un borde. Proporcione un algoritmo O (n^3) para encontrar un ciclo dirigido en G del peso total mínimo. Se dará crédito parcial para un algoritmo O ((n^2) * m).

---

Aquí es mi algoritmo.

Hago un DFS. Cada vez que encuentro un back edge, sé que tengo un ciclo dirigido.

Luego iré temporalmente hacia atrás por el parent array (hasta que viaje a través de todos los vértices en el ciclo) y calcule el total weights.

Luego comparo el total weight de este ciclo con min. min siempre toma el peso total mínimo. Después de que el DFS finaliza, también se encuentra nuestro ciclo dirigido mínimo.

---

Bien, entonces sobre el tiempo la complejidad.

Para ser sincero, no sé la complejidad temporal de mi algoritmo.

Para DFS, el recorrido toma O (m + n) (si m es el número de aristas yn es el número de vértices). Para cada vértice, podría apuntar a uno de sus antepasados ​​y así formar un ciclo. Cuando se encuentra un ciclo, se necesita O (n) para resumir los pesos totales.

Así que creo que el tiempo total es O (m + n * n). Pero obviamente está mal, como se establece en el impuesto especial, el tiempo óptimo es O (n^3) y el tiempo normal es O (m * n^2).

---

¿Puede alguien ayudarme con:

1. ¿Es mi algoritmo correcto?
2. ¿Cuál es la complejidad del tiempo si mi algoritmo es correcto?
3. ¿Hay algún algoritmo mejor para este problema?

Answer 1

puede utilizar Floyd-Warshall algoritmo aquí.

El algoritmo de Floyd-Warshall encuentra camino más corto entre todos los pares de vértices

El algoritmo es entonces muy simple, repase todos los pares (u,v), y encuentre el par que minimizó dist(u,v)+dist(v,u), ya que este par indica en un ciclo de u a u con peso dist(u,v)+dist(v,u). Si el gráfico también permite bucles automáticos (un borde (u,u)), también deberá verificarlos solos, porque esos ciclos (y solo ellos) no fueron verificados por el algoritmo.

seudo código:

run Floyd Warshall on the graph 
min <- infinity 
vertex <- None 
for each pair of vertices u,v 
    if (dist(u,v) + dist(v,u) < min): 
      min <- dist(u,v) + dist(v,u) 
      pair <- (u,v) 
return path(u,v) + path(v,u) 

path(u,v) + path(v,u) es en realidad la ruta encontrado de u a v y, a continuación de V a u, que es un ciclo.

El tiempo de ejecución del algoritmo es O(n^3), ya que floyd-warshall es el cuello de la botella, ya que el ciclo tarda O(n^2).

Creo que la precisión aquí es trivial, pero avíseme si no está de acuerdo conmigo y trataré de explicarlo mejor.

Answer 2

"para cada vértice, se podría señalar de nuevo a uno de sus antepasados, y forma así un ciclo de"

creo que podría señalar de nuevo a cualquiera de sus ascendientes que significa N

También, ¿Cómo vas a marcar vértices cuando salgas de sus dfs, puedes volver allí desde otro vértice y va a ser otro ciclo? Entonces esto ya no es (n + m) dfs.

1. Así ur algo está incompleto
2. mismo aquí

3. Durante un dfs, creo que el vértice debe ser invisible, o verificarlo, y para comprobarlo, puede almacenar el peso mínimo para la ruta al vértice inicial. Entonces, si en alguna otra etapa encuentras una ventaja en ese vértice, ya no tienes que buscar esta ruta. Este dfs encontrará el ciclo dirigido mínimo que contiene el primer vértice. y es O (n^2) (O (n + m) si almacena el gráfico como una lista)

Entonces si hacerlo desde cualquier otro vértice será O (n^3) (O (n * (n + m))

lo sentimos, por mi Inglés y yo no soy bueno en la terminología

Answer 3

¿Mi algoritmo es correcto?

No. Déjame dar un ejemplo de contador. Imagínese que se inicia a partir de DFS u, hay dos caminos p1 y p2 de u a v y 1 ruta de p3v volver a u, p1 es más corta que p2.

Supongamos que inicie tomando el camino p2 a v, y caminar de regreso a u por ruta p3. Se encontró un ciclo pero aparentemente no es mínimo. Luego continúe explorando u tomando la ruta p1, pero como se explora completamente el v, el DFS finaliza sin encontrar el ciclo mínimo.