[ALGORITMI] Grafi
ciao, devo risolvere questo problema sul quale mi sono incastrato da ore, vi incollo il testo:
Si consideri un grafo orientato pesato. Si supponga che il peso sugli archi possa valere
solamente 1, 2 oppure 3. Si vuole calcolare il percorso più breve da un nodo di partenza verso
un nodo di destinazione. Si valuti, attraverso la definizione di algoritmi opportuni e la loro
analisi di complessità, se convenga o meno trasformare il grafo iniziale in un grafo non pesato
con cammini composti rispettivamente da 1, 2, e 3 archi.
Quello che ho pensato io è questo:
se il grafo è pesato posso applicare l'algoritmo di Dijkstra che ha una complessità O(V+E)logE
se il grafo non è pesato il libro mi dice che posso utilizzare l'algoritmo BFS, però il problema che questo algoritmo di complessità O(v+E) dipende dal numero di archi e nodi.
Nel caso migliore se tutti gli archi avessero peso 1 nel trasformarlo in non pesato il BFS sarebbe il più efficiente, ma se gli archi pesassero tutti 2 o 3 come faccio a calcolare V e E per poi valutarne la complessità?
Avete qualche suggerimento?
una seconda domanda, ma scrivere O(V+E)logE equivale a dire che la complessità è nlogn?
grazie mille per qualsiasi aiuto
Si consideri un grafo orientato pesato. Si supponga che il peso sugli archi possa valere
solamente 1, 2 oppure 3. Si vuole calcolare il percorso più breve da un nodo di partenza verso
un nodo di destinazione. Si valuti, attraverso la definizione di algoritmi opportuni e la loro
analisi di complessità, se convenga o meno trasformare il grafo iniziale in un grafo non pesato
con cammini composti rispettivamente da 1, 2, e 3 archi.
Quello che ho pensato io è questo:
se il grafo è pesato posso applicare l'algoritmo di Dijkstra che ha una complessità O(V+E)logE
se il grafo non è pesato il libro mi dice che posso utilizzare l'algoritmo BFS, però il problema che questo algoritmo di complessità O(v+E) dipende dal numero di archi e nodi.
Nel caso migliore se tutti gli archi avessero peso 1 nel trasformarlo in non pesato il BFS sarebbe il più efficiente, ma se gli archi pesassero tutti 2 o 3 come faccio a calcolare V e E per poi valutarne la complessità?
Avete qualche suggerimento?
una seconda domanda, ma scrivere O(V+E)logE equivale a dire che la complessità è nlogn?
grazie mille per qualsiasi aiuto
Risposte
Premetto che sto studiando anche io la parte dei grafi, quindi leggimi con spirito critico 
.
La complessità [nota]per E intendo gli archi e per V i nodi, o vertici[/nota] dell'algoritmo di Dijkstra è caratterizzata da $O(|V|)$ (inizializzazione) + $O(|V|)$ (costrutire la min Heap) + $O(|V|log|V|)$ (estrarre |V| volte il minimo dalla heap) + $O(|E|log|V|)$ (rilassare i nodi e modificare la heap).
Dunque la complessità finale, visto che è una sommatoria, è la più grande che abbiamo incontrato: se $|V|>|E|$ allora la complessità sarà $O(|E|log|V|)$, viceversa sarà $O(|V|log|V|)$. Per questo nella formula che hai scritto scegli il più grande fra E e V. Quindi come forma è equivalente a dire nlogn.
Comunque se il grafo è pesato puoi applicare Dijkstra. Ma una volta terminato, hai calcolato il cammino minimo per tutti i nodi, quindi devi ancora trovare quello che cerchi.
Se il grafo non è pesato puoi applicare BFS, ma visto che sai che al massimo i cammini saranno moltiplicati per tre la complessità risulta $O(|V|+3|E|)$ che però è equivalente ad $O(|V|+|E|)$ perché hai moltiplicato per una costante.
Spero di non aver fatto errori.
."mrmoon":
una seconda domanda, ma scrivere O(V+E)logE equivale a dire che la complessità è nlogn?
La complessità [nota]per E intendo gli archi e per V i nodi, o vertici[/nota] dell'algoritmo di Dijkstra è caratterizzata da $O(|V|)$ (inizializzazione) + $O(|V|)$ (costrutire la min Heap) + $O(|V|log|V|)$ (estrarre |V| volte il minimo dalla heap) + $O(|E|log|V|)$ (rilassare i nodi e modificare la heap).
Dunque la complessità finale, visto che è una sommatoria, è la più grande che abbiamo incontrato: se $|V|>|E|$ allora la complessità sarà $O(|E|log|V|)$, viceversa sarà $O(|V|log|V|)$. Per questo nella formula che hai scritto scegli il più grande fra E e V. Quindi come forma è equivalente a dire nlogn.
Comunque se il grafo è pesato puoi applicare Dijkstra. Ma una volta terminato, hai calcolato il cammino minimo per tutti i nodi, quindi devi ancora trovare quello che cerchi.
Se il grafo non è pesato puoi applicare BFS, ma visto che sai che al massimo i cammini saranno moltiplicati per tre la complessità risulta $O(|V|+3|E|)$ che però è equivalente ad $O(|V|+|E|)$ perché hai moltiplicato per una costante.
Spero di non aver fatto errori.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo