Devo implementare l'algoritmo di Dijkstra. Per farlo serve un heap: La libreria stl prevede l'heap, ma non sono implementate le operazioni decrease key, increase key. Devo crearmi l'heap da per me da zero o è possibile utilizzare qualche altro sistema?
Ok...Ho capito che devo implementarmelo da zero...
mi inserisco di straforo,
ti volevo chiedere se per gestire l albero usi un vettore statico o un vettore dinamico. Da quanto letto in Internet l heap dovrebbe potersi fare anche con un vettore statico...confermi?
Io utilizzo il vector per facilitarmi la vita. Certo che si puo' usare anche un array classico del c.
premetto che non so come sia fatto questo algoritmo... però non so fino a che punto convenga farlo statico il vettore (a meno che l'algoritmo non lo permetta...).. comunque questo "problema" è facilmente aggirabile con una malloc o una calloc....
http://gauguin.info.uniroma2.it/~ita...doc/index.html
Questa è una libreria di algoritmi e strutture dati in C++ che il prof di ASD appunto insieme a degli studenti ha realizzato. E' ancora in sviluppo e estremamente collegata al libro indicato (il libro che si usa nel corso di ASD a Tor Vergata). E' open source e penso ti sarà mooooooooolto utile.
Ciao ciao
Grazie del consiglio.
Ecco la risposta: si utilizza un priority_queue. Quando si vuole abbassare il valore della distanza di un vertice, si inserisce un nuovo valore nella struttura. Poi, ogni volta che si seleziona un nuovo vertice all'interno del ciclo, si verifica che quel vertice non sia già uscito in precedenza.
A proposito... La priority_queue utilizza internamente un heap o una lista?
Non vorrei sbagliarmi... ma dovrebbe essere uno heap... ordinato in base alla chiave (o priorità) assegnata a un determinato elemento...
Permessi di invio
Rispondi quotando