Problema su algoritmo di Dijkstra
Avrei bisogno di una soluzione per questo problema:
Discuti se l'algoritmo di Dijkstra funziona ancora nel caso in cui esistono archi di costo negativo nel grafo ,ma tutti gli archi di costo negativo escono dalla sorgente .Nel caso di risposta affermativa fornisci una dimostrazione formale ,nel caso di risposta negativa mostra un controesempio .Motiva esaurientemente le tue risposte.
Io avevo pensato NO, ma non riesco a dire il perchè .Se potete aiutarmi mi fareste un grande favore,visto che ho l'esame fra pochi giorni
Discuti se l'algoritmo di Dijkstra funziona ancora nel caso in cui esistono archi di costo negativo nel grafo ,ma tutti gli archi di costo negativo escono dalla sorgente .Nel caso di risposta affermativa fornisci una dimostrazione formale ,nel caso di risposta negativa mostra un controesempio .Motiva esaurientemente le tue risposte.
Io avevo pensato NO, ma non riesco a dire il perchè .Se potete aiutarmi mi fareste un grande favore,visto che ho l'esame fra pochi giorni
Risposte
Prima di tutto, ti chiedo un chiarimento sul testo del problema. Con "ma tutti gli archi di costo negativo escono dalla sorgente", intendi dire che gli archi con costo negativo hanno tutti come nodo di origine quello scelto come origine dei cammini di costo minimo nell'algoritmo di Dijkstra?
Per la risoluzione dell'esercizio ti invito a prendere in considerazione l'algoritmo di Dijkstra e gli invarianti che vengono mantenuti ad ogni passo dell'algoritmo. Questi invarianti vengono mantenuti anche nel caso sopra citato? Se non è così, questa osservazione dovrebbe permetterti di trovare un controesempio.
Per la risoluzione dell'esercizio ti invito a prendere in considerazione l'algoritmo di Dijkstra e gli invarianti che vengono mantenuti ad ogni passo dell'algoritmo. Questi invarianti vengono mantenuti anche nel caso sopra citato? Se non è così, questa osservazione dovrebbe permetterti di trovare un controesempio.
da quanto ricordo se dalla sorgente escono solo archi di peso negativo (i vertici interni dovrebbero esser tutti positivi o non formare strani cicli) l'algoritmo si dimostra che può concludere.
Se invece gli archi di peso negativo sono nei vertici interni e dalla sorgente escono pesi positivi allora l'algoritmo fallirà.
Se invece gli archi di peso negativo sono nei vertici interni e dalla sorgente escono pesi positivi allora l'algoritmo fallirà.
Sì, è quello che in effetti mi dice l'intuizione (credo che i pesi in uscita dalla sorgente possano però essere anche positivi e non solo negativi).
ci sono ulteriori condizioni da porre, perchè un solo arco di peso negativo può essere sufficiente per avere un ciclo di peso negativo e far sballare tutto...
si come dice il testo, tutti gli archi di costo negativo escono dalla sorgente,quindi gli altri saranno positivi.
Quindi alla fine come dimostro che è vero ,oppure se è sbagliato.Nel testo dice di fornire una dimostrazione oppure un controesempio nell'altro caso.
Grazie mille in anticipo
Quindi alla fine come dimostro che è vero ,oppure se è sbagliato.Nel testo dice di fornire una dimostrazione oppure un controesempio nell'altro caso.
Grazie mille in anticipo
Ma ti ho già dato qualche consiglio.. come dimostri la validità dell'algoritmo di Dijkstra nel caso in cui tutti gli archi sono positivi?
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo