# 2 problemi nell'implementazione dijkstra

**URL:** <https://forum.olinfo.it/t/2-problemi-nellimplementazione-dijkstra/5490>\
**Category:** Aiuto\
**Created:** [24 Dicembre 2018, 3:02pm UTC](https://forum.olinfo.it/t/2-problemi-nellimplementazione-dijkstra/5490 "2018-12-24T15:02:45Z")\
**Posts on this page:** 20\
**Page:** 1

<div class="post-metadata">

**Author:** ![shine](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/s/77aa72/32.png) [@shine](https://forum.olinfo.it/u/shine)\
**Post date:** [24 Dicembre 2018, 3:02pm UTC](https://forum.olinfo.it/t/2-problemi-nellimplementazione-dijkstra/5490/1 "2018-12-24T15:02:45Z")

</div>

[https://pastebin.com/BxV2KBmd](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!

---

<div class="post-metadata">

**Author:** ![v.bizzarri](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/v/7c8e57/32.png) [@v.bizzarri](https://forum.olinfo.it/u/v.bizzarri)\
**Post date:** [24 Dicembre 2018, 3:13pm UTC](https://forum.olinfo.it/t/2-problemi-nellimplementazione-dijkstra/5490/2 "2018-12-24T15:13:11Z")

</div>

> [@shine](#):
>
> q.push({w.first,-distanze[w.first]});

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

---

<div class="post-metadata">

**Author:** ![shine](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/s/77aa72/32.png) [@shine](https://forum.olinfo.it/u/shine)\
**Post date:** [24 Dicembre 2018, 3:20pm UTC](https://forum.olinfo.it/t/2-problemi-nellimplementazione-dijkstra/5490/3 "2018-12-24T15:20:24Z")

</div>

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.  
"

---

<div class="post-metadata">

**Author:** ![frakkiobello](https://forum.olinfo.it/user_avatar/forum.olinfo.it/frakkiobello/32/2768_2.png) [@frakkiobello](https://forum.olinfo.it/u/frakkiobello)\
**Post date:** [24 Dicembre 2018, 3:51pm UTC](https://forum.olinfo.it/t/2-problemi-nellimplementazione-dijkstra/5490/4 "2018-12-24T15:51:48Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![shine](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/s/77aa72/32.png) [@shine](https://forum.olinfo.it/u/shine)\
**Post date:** [24 Dicembre 2018, 3:55pm UTC](https://forum.olinfo.it/t/2-problemi-nellimplementazione-dijkstra/5490/5 "2018-12-24T15:55:42Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![frakkiobello](https://forum.olinfo.it/user_avatar/forum.olinfo.it/frakkiobello/32/2768_2.png) [@frakkiobello](https://forum.olinfo.it/u/frakkiobello)\
**Post date:** [24 Dicembre 2018, 4:21pm UTC](https://forum.olinfo.it/t/2-problemi-nellimplementazione-dijkstra/5490/6 "2018-12-24T16:21:04Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![shine](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/s/77aa72/32.png) [@shine](https://forum.olinfo.it/u/shine)\
**Post date:** [24 Dicembre 2018, 4:22pm UTC](https://forum.olinfo.it/t/2-problemi-nellimplementazione-dijkstra/5490/7 "2018-12-24T16:22:50Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![frakkiobello](https://forum.olinfo.it/user_avatar/forum.olinfo.it/frakkiobello/32/2768_2.png) [@frakkiobello](https://forum.olinfo.it/u/frakkiobello)\
**Post date:** [24 Dicembre 2018, 4:25pm UTC](https://forum.olinfo.it/t/2-problemi-nellimplementazione-dijkstra/5490/8 "2018-12-24T16:25:50Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![shine](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/s/77aa72/32.png) [@shine](https://forum.olinfo.it/u/shine)\
**Post date:** [24 Dicembre 2018, 4:26pm UTC](https://forum.olinfo.it/t/2-problemi-nellimplementazione-dijkstra/5490/9 "2018-12-24T16:26:42Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![frakkiobello](https://forum.olinfo.it/user_avatar/forum.olinfo.it/frakkiobello/32/2768_2.png) [@frakkiobello](https://forum.olinfo.it/u/frakkiobello)\
**Post date:** [24 Dicembre 2018, 4:27pm UTC](https://forum.olinfo.it/t/2-problemi-nellimplementazione-dijkstra/5490/10 "2018-12-24T16:27:43Z")

</div>

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?

---

<div class="post-metadata">

**Author:** ![shine](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/s/77aa72/32.png) [@shine](https://forum.olinfo.it/u/shine)\
**Post date:** [24 Dicembre 2018, 4:28pm UTC](https://forum.olinfo.it/t/2-problemi-nellimplementazione-dijkstra/5490/11 "2018-12-24T16:28:47Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![frakkiobello](https://forum.olinfo.it/user_avatar/forum.olinfo.it/frakkiobello/32/2768_2.png) [@frakkiobello](https://forum.olinfo.it/u/frakkiobello)\
**Post date:** [24 Dicembre 2018, 4:30pm UTC](https://forum.olinfo.it/t/2-problemi-nellimplementazione-dijkstra/5490/12 "2018-12-24T16:30:57Z")

</div>

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.

---

<div class="post-metadata">

**Author:** ![shine](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/s/77aa72/32.png) [@shine](https://forum.olinfo.it/u/shine)\
**Post date:** [24 Dicembre 2018, 4:31pm UTC](https://forum.olinfo.it/t/2-problemi-nellimplementazione-dijkstra/5490/13 "2018-12-24T16:31:42Z")

</div>

Allora provo subito!

---

<div class="post-metadata">

**Author:** ![shine](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/s/77aa72/32.png) [@shine](https://forum.olinfo.it/u/shine)\
**Post date:** [24 Dicembre 2018, 4:43pm UTC](https://forum.olinfo.it/t/2-problemi-nellimplementazione-dijkstra/5490/14 "2018-12-24T16:43:52Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![shine](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/s/77aa72/32.png) [@shine](https://forum.olinfo.it/u/shine)\
**Post date:** [24 Dicembre 2018, 6:30pm UTC](https://forum.olinfo.it/t/2-problemi-nellimplementazione-dijkstra/5490/15 "2018-12-24T18:30:38Z")

</div>

Ho provato anche con long long ma non cambia nulla

---

<div class="post-metadata">

**Author:** ![v.bizzarri](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/v/7c8e57/32.png) [@v.bizzarri](https://forum.olinfo.it/u/v.bizzarri)\
**Post date:** [25 Dicembre 2018, 12:47am UTC](https://forum.olinfo.it/t/2-problemi-nellimplementazione-dijkstra/5490/16 "2018-12-25T00:47:23Z")

</div>

> 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?

---

<div class="post-metadata">

**Author:** ![shine](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/s/77aa72/32.png) [@shine](https://forum.olinfo.it/u/shine)\
**Post date:** [25 Dicembre 2018, 12:52am UTC](https://forum.olinfo.it/t/2-problemi-nellimplementazione-dijkstra/5490/17 "2018-12-25T00:52:44Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![v.bizzarri](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/v/7c8e57/32.png) [@v.bizzarri](https://forum.olinfo.it/u/v.bizzarri)\
**Post date:** [25 Dicembre 2018, 2:01am UTC](https://forum.olinfo.it/t/2-problemi-nellimplementazione-dijkstra/5490/18 "2018-12-25T02:01:29Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![frakkiobello](https://forum.olinfo.it/user_avatar/forum.olinfo.it/frakkiobello/32/2768_2.png) [@frakkiobello](https://forum.olinfo.it/u/frakkiobello)\
**Post date:** [25 Dicembre 2018, 9:58am UTC](https://forum.olinfo.it/t/2-problemi-nellimplementazione-dijkstra/5490/19 "2018-12-25T09:58:55Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![shine](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/s/77aa72/32.png) [@shine](https://forum.olinfo.it/u/shine)\
**Post date:** [25 Dicembre 2018, 11:02am UTC](https://forum.olinfo.it/t/2-problemi-nellimplementazione-dijkstra/5490/20 "2018-12-25T11:02:08Z")

</div>

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?

[Pagina seguente](https://forum.olinfo.it/t/2-problemi-nellimplementazione-dijkstra/5490.md?page=2)