Se parliamo delle territoriali (come nel caso del task footing) allora è importante far notare che l’efficienza non è fondamentale. È importante solo che l’algoritmo sia corretto (e ragionevolmente performante, nel senso: non terribilmente esponenziale). Una soluzione per footing che qui esce dai limiti di tempo, avrebbe tranquillamente preso tutti i punti in gara. Il tempo limite alle territoriali è volutamente alto per far passare soluzioni non efficienti.
Se invece parliamo di altre gare, allora la regola è la solita: calcolare la complessità, stimare il tempo d’esecuzione al caso pessimo. Dijkstra (nell’implementazione che conosco io, quella spiegata nel booklet che contiene il task footing) è O(M\log N) dove M è il num di archi e N il num di nodi.
Scusate l’ignoranza, so come funziona l’algoritmo di dijkstra ma non capisco come è possibile utilizzarlo per rilevare il ciclo minimo all’interno di un grafo.
Qualcuno me lo potrebbe spiegare?
Il ciclo in un grafo equivale ad il cammino minimo tra A e B (senza passare per l’arco A-B) e la somma dell’arco stesso.
L’unica modifica che devi applicare a dijkstra è quella per cui quando inserisci nella coda i vari nodi adiacenti, controlli che il nodo attuale non sia A e il nodo collegato non sia B. Se dijkstra ti restituirà INFINITO vuol dire che non esiste un ciclo tra i 2 nodi.
È super-necroposting, ma vabbè, leggo ora e volevo aggiungere un paio di cose. Per quanto riguarda il problema Dijkstra sul CMS, la soluzione con tempo minore fatta da Zappia è il classico algoritmo di Dijkstra scritto in Assembly; il secondo tempo migliore è un codice sottomesso da me, dove implemento SPFA al posto di Dijkstra. Quindi nei grafi sparsi, SPFA è veramente più efficiente.
