2 problemi nell'implementazione dijkstra


#1

https://pastebin.com/BxV2KBmd
Salve, sto provando in questi giorni a implementare l’algoritmo di dijkstra e ho trovato un pdf da cui ho preso spunto ma ci sono due problemi:
1 Non riesco a capire cosa succede in questa parte:
for (auto w : v[corrente]) {
if (distanze[corrente]+w.second < distanze[w.first]) {
distanze[w.first] = distanze[corrente]+w.second;
q.push({w.first,-distanze[w.first]});
}
}

2 Nel problema omonimo risolve solo due task, negli altri sfora il tempo, cosa devo migliorare nel problema?

Grazie mille in anticipo!


#2

-distanze[w.first] ?? ci metti il meno?


#3

Sì, perché il priority queue mette i valori più grandi all’inizio e mettendo il meno posso invertirlo, non so se mi sono spiegato, nel dubbio ti metto la spiegazione del pdf:
"A small difficulty is that in Dijkstra’s algorithm, we should find the node with the
minimum distance, while the C++ priority queue finds the maximum element as
default. An easy trick is to use negative distances, which allows us to directly use
the C++ priority queue.
"


#4

Se tu dichiari la priority queue come :
priority_queue< pair< int , int > , vector <pair < int, int > >, greater < pair<int , int > > > non hai quel problema.


#5

E poi posso usarla facilmente con un q.first e un q.second?


#6

Certo, l’unica differenza è che li ordina in modo crescente


#7

ok, grazie mille, lo userò.
Per il resto, hai qualche consiglio?


#8

Utilizza i long long int, altrimenti prendi wa.
Per il resto sembra ok.


#9

Wa?
Comunque, non credo sia quello il problema visto che per adesso totalizzo 10/100 in dijkstra


#10

WA significa wrong answer, quindi output errato:
Hai fatto qualche prova in locale per cedere se l’algoritmo fa effettivamente ciò che gli chiedi di fare?


#11

In locale, sì e poi riesco a risolvere due task, l’unico problema è che ci mette molto e non capisco perché, nel pdf leggo che invece è molto veloce


#12

Infatti dovrebbe esserlo, primo consiglia prova a riscriverlo meglio, senza i meno e a ripostare. Fra poco dovrei avere qualche minuto per leggere bene il codice.


#13

Allora provo subito!


#14

https://pastebin.com/ypk24xZv
15/100 ma stavolta i task che non risolvo mi dà output non corretto e non execution timed out


#15

Ho provato anche con long long ma non cambia nulla


#16

corrente=q.top().second;

if(distanze[corrente]+y.second<distanze[y.first]){
distanze[y.first]=distanze[corrente]+y.second;

Mi sbaglio o sommi le distanze con i nodi?


#17

Non mi sembra, y.second, che è uguale a v[].second, sono i pesi degli archi


#18

hai ragione scusa, ma forse il problema è che il testo tratta di un grafo diretto ma tu lo tratti come un grafo non diretto

v[a].push_back({b,c});
v[b].push_back({a,c});

togliendo il secondo push_back fa 95/100, se vuoi far 100/100 utilizza i consigli sui long long di @frakkiobello


#19

Ho guardato, modificato e provato il codice per 30 minuti senza accorgermene :smile:


#20

Grazie mille, ora posso stare più tranquillo sapendo usare dijkstra pero non capisco:da cosa nel testo si capisce che tratta di archi diretti? O forse è una condizione dell’algoritmo in sé che forse ho tralasciato?