Aquí hay un impuesto especial:
Sea G una gráfica dirigida ponderada con nVértices y m aristas, donde todos los aristas tienen 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 un DFS. Cada vez que encuentro un back edge, Sé que tengo un ciclo dirigido.
Luego iré temporalmente hacia atrás a lo largo del parent array (hasta que viaje a través de todos los vértices en el ciclo) y calculo la total weights.
Luego comparo el total weight de este ciclo con min. 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 de tiempo de mi algoritmo.
Para DFS, el recorrido toma O (m + n) (si m es elnúmero de aristas, 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 está mal, como se indica en el impuesto especial, el tiempo óptimo es O (n ^ 3) y el tiempo normal es O (m * n ^ 2).
¿Alguien puede ayudarme con:
- ¿Es correcto mi algoritmo?
- ¿Cuál es la complejidad del tiempo si mi algoritmo es correcto?
- ¿Hay algún algoritmo mejor para este problema?
Respuestas
19 para la respuesta № 1Puedes usar Floyd-Warshall algoritmo aquí
El algoritmo Floyd-Warshall encuentra el camino más corto entre todas las parejas de vértices.
El algoritmo es entonces muy simple, repasar todos los pares. (u,v)y encuentra el par que minimiza dist(u,v)+dist(v,u), ya que este par indica en un ciclo desde u a u con peso dist(u,v)+dist(v,u). Si el gráfico también permite auto-bucles (un borde (u,u)), también deberá verificarlos solos, porque el algoritmo no verificó esos ciclos (y solo ellos).
pseudo codigo
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 el camino encontrado de u a v y luego 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 bucle toma O(n^2) hora.
Creo que la corrección aquí es trivial, pero hazme saber si no estás de acuerdo conmigo y trataré de explicarlo mejor.
2 para la respuesta № 2
"Para cada vértice, puede apuntar a uno de sus antepasados y así formar un ciclo"
Creo que podría apuntar a cualquiera de sus ancestros, lo que significa N
Además, ¿cómo vas a marcar los vértices cuando saliste de su dfs? Puedes volver a hacerlo desde otro vértice y será otro ciclo. Así que esto ya no es (n + m) dfs.
- Así que tu algo está incompleto
- igual que aquí
3. Durante un dfs, creo que el vértice debería estar oculto, o chequear, y para verificarlo, puede almacenar el peso mínimo para la ruta hacia el vértice inicial. Por lo tanto, si en alguna otra etapa encuentra un borde para ese vértice, ya no tendrá que buscar este camino. Este dfs encontrará el ciclo mínimo dirigido que contiene el primer vértice. y es O (n ^ 2) (O (n + m) si u almacena el gráfico como lista)
Entonces, si hacerlo desde cualquier otro vértice será O (n ^ 3) (O (n * (n + m))
Lo siento, por mi inglés y no soy bueno en terminología
2 para la respuesta № 3
¿Es correcto mi algoritmo?
No. Déjame dar un ejemplo de contador. Imagina que inicias DFS desde u, hay dos caminos p1 y p2 de u a v y 1 camino p3 de v de regreso u, p1 es más corto que p2.
Supongamos que comienza por tomar el p2 camino a v, y caminar de regreso a u por camino p3. Se encontró un ciclo, pero aparentemente no es mínimo. Luego continúas explorando u tomando el p1 camino, pero desde v está completamente explorado, el DFS termina sin encontrar el ciclo mínimo.