Aquí hay un impuesto especial:

Sea G un gráfico 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. Dé un algoritmo O (n ^ 3) para encontrar un ciclo dirigido en G del peso total mínimo. Se otorgará crédito parcial por un algoritmo O ((n ^ 2) * m).

Aquí está mi algoritmo.

hago unDFS. Cada vez que encuentro unback edgeSé que tengo un ciclo dirigido.

Luego iré temporalmente hacia atrás a lo largo delparent array (hasta que viaje a través de todos los vértices en el ciclo) y calculo latotal weights.

Luego comparo eltotal weight de este ciclo conmin. min Siempre toma los pesos totales mínimos. Una vez finalizado el DFS, también se encuentra nuestro ciclo mínimo dirigido.

Ok, entonces sobre la complejidad del tiempo.

Para ser honesto, no sé la complejidad del tiempo de mi algoritmo.

Para DFS, el recorrido toma O (m + n) (si m es el número de bordes y n es el número de vértices). Para cada vértice, puede apuntar a uno de sus antepasados ​​y, por lo tanto, forma 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, es incorrecto, como se indica en el impuesto especial, el tiempo óptimo es O (n ^ 3) y el tiempo normal es O (m * n ^ 2).

¿Alguien me puede ayudar con:

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