Ciclo minimo in un grafo

Ciao, molti esercizi sul cms sono di calcolo del ciclo minimo in un grafo orientato e non. Come per esempio Corsa Mattutina. Conoscendo dijkstra mi viene da usarlo; ma il problema è che io l’ho sempre usato per calcolare il cammino minimo tra 2 nodi differenti. Conoscete qualche variante o qualche algoritmo simile che me lo calcoli?

Per il calcolo del ciclo minimo, basta che tu lo applichi l’algoritmo su 2 nodi differenti che siano collegati tra di loro e facendo in modo che quando inserisci nella coda o nel set i vari nodi controlli che il nodo attuale sia diverso dal nodo iniziale e che il nodo da inserire sia diverso da quello finale.

[spoiler]
(pseudocodice - si presume che questo vada all’interno di un ciclo for)
i sta per il nodo i-esimo che si vuole controllare

if(attuale == inizio && i == fine)
continue;[/spoiler]

aspetta non ti seguo, io per dijkstra uso una coda con priorità e come condizione di uscita non appena visito il nodo finale. Essendo in questo caso il nodo finale il nodo iniziale stesso non va bene perché uscirebbe subito. Quindi cosa faccio?

Al posto di dargli come fine il nodo iniziale i gli dai invece il nodo j del collegamento i - j e ritorni il valore del nodo j + arco(i, j). Praticamente cerchi il cammino minimo tra i - j senza passare per quel collegamento e poi ritorni la somma tra il valore minimo del nodo j e il peso di quell’arco.

teoricamente però per non escludermi nessuna soluzione dovrei farlo per ogni nodo adiacente a i e poi dovrei prendere quello con valore più piccolo :sweat_smile:

Esatto, o più semplicemente (per evitare di ripetere un controllo i,j quando farai j,i) ti basta iterare su tutti gli archi del grafo e poi usare i due estremi dell’arco come partenza e arrivo.

1 Mi Piace

Alla fine non è nulla di così complesso solo che secondo me non è proprio geniale… Io cercavo qualcosa di più “diretto” diciamo😅

Così esegui |E| volte l’algoritmo di Dijkstra (O( (|V|+|E|)\log (|V|+|E|))).
Sì può trovare il ciclo minimo chiamandolo solo |V| volte.

cioè? quale sarebbe l’algoritmo

Lancio Dijkstra da ogni nodo.
Dentro Dijkstra, ogni volta che sto esaminando i vicini del nodo u, per cercare di migliorare le loro distanze, se non riesco a migliorare il nodo v, allora posso dire che esiste un ciclo non più lungo di dst[u]+dst[v]+arco(u,v).lenght
Ho dimostrato che il ciclo minimo può essere trovato in questo modo.