grafico - Come trovare il ciclo minimo diretto (peso totale minimo)?

Question

Ecco un'accisa:

Sia G un grafo orientato zavorrato con n vertici e m bordi, dove tutti i bordi hanno un peso positivo. Un ciclo diretto è un percorso diretto che inizia e finisce nello stesso vertice e contiene almeno un bordo. Dare un algoritmo O (n^3) per trovare un ciclo diretto in G di peso totale minimo. Verrà fornito un credito parziale per un algoritmo O ((n^2) * m).

---

Ecco il mio algoritmo.

Faccio uno DFS. Ogni volta che trovo uno back edge, so di avere un ciclo diretto.

Quindi passerò temporaneamente indietro lungo lo parent array (fino a quando percorrerò tutti i vertici del ciclo) e calcolerò lo total weights.

Quindi confronto lo total weight di questo ciclo con min. min prende sempre il peso totale minimo. Al termine del DFS, viene trovato anche il nostro ciclo minimo diretto.

---

Ok, quindi circa la complessità del tempo.

Per essere onesto, non conosco la complessità temporale del mio algoritmo.

Per DFS, l'attraversamento prende O (m + n) (se m è il numero di spigoli e n è il numero di vertici). Per ogni vertice, potrebbe puntare a uno dei suoi antenati e quindi formare un ciclo. Quando viene trovato un ciclo, prende O (n) per riassumere i pesi totali.

Quindi penso che il tempo totale sia O (m + n * n). Ma ovviamente è sbagliato, come indicato nell'accisa il tempo ottimale è O (n^3) e il tempo normale è O (m * n^2).

---

Qualcuno mi può aiutare con:

1. È il mio algoritmo corretto?
2. Qual è la complessità temporale se il mio algoritmo è corretto?
3. Esiste un algoritmo migliore per questo problema?

Answer 1

È possibile utilizzare Floyd-Warshall algoritmo qui.

L'algoritmo di Floyd-Warshall trova più breve percorso tra tutte le coppie di vertici.

L'algoritmo è quindi molto semplice, andare su tutte le coppie (u,v) e trovare la coppia che ha ridotto al minimo dist(u,v)+dist(v,u), poiché questa coppia indica su un ciclo da u a u con peso dist(u,v)+dist(v,u). Se il grafico consente anche i self-loops (un fronte (u,u)), dovrai anche controllarli da soli, perché quei cicli (e solo loro) non sono stati controllati dall'algoritmo.

pseudo codice:

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) è in realtà il percorso trovato da u a v e poi da v a u, che è un ciclo.

L'ora di esecuzione dell'algoritmo è O(n^3), poiché floyd-warshall è il collo della bottiglia, poiché il ciclo prende il tempo O(n^2).

Penso che la correttezza qui sia banale, ma fammi sapere se non sei d'accordo con me e cercherò di spiegarlo meglio.

Answer 2

"Per ogni vertice, potrebbe indicare tornare a uno dei suoi antenati e quindi costituisce un ciclo"

Credo che potrebbe indicare ritorna qualsiasi suo antenato che significa N

Inoltre, come andrai a segnare i vertici quando uscirai dal suo dfs, potresti tornare di nuovo da un altro vertice e il suo sarà un altro ciclo. Quindi questo non è più (n + m) dfs.

1. Quindi ur algo è incompleta
2. stesso qui

3. Durante un dfs, penso che il vertice debba essere non visto, o controllare, e per quanto controllato puoi memorizzare il peso minimo per il percorso del vertice di partenza. Quindi, se in qualche altro stadio trovi un limite a quel vertice, non devi più cercare questo percorso. Questo dfs troverà il ciclo diretto minimo contenente il primo vertice. ed è O (n^2) (O (n + m) se memorizzi il grafico come lista)

Quindi, se farlo da qualsiasi altro vertice, sarà O (n^3) (O (n * (n + m))

Siamo spiacenti, per il mio inglese e io non sono bravo a terminologia

Answer 3

Il mio algoritmo è corretto?

No. Consentitemi di dare un esempio. Immaginate di iniziare DFS da u, ci sono due percorsi p1 e p2 da u a v e 1 percorso p3 da v torna a u, p1 è più breve di p2.

Supporre di iniziare prendendo il percorso p2 a v e tornare a u dal percorso p3. Un ciclo trovato ma a quanto pare non è minimo. Quindi si continua a esplorare u prendendo il percorso p1, ma poiché lo v è stato completamente esplorato, il DFS termina senza trovare il ciclo minimo.