Algoritmo di Dijkstra: differenze tra le versioni

Versione delle 12:42, 7 nov 2019

Versione delle 10:28, 15 dic 2020

Riga 82:

In generale, la complessità, <math>T_D(G)</math>, dell'algoritmo di Dijkstra è limitata superiormente da

:<math>T_D(G) = \Theta(|V|) + T_B(|V|) + |V| * T_E(|V|) + |E| * T_U(|V|)</math>

dove <math>T_B(|V|)</math>, <math>T_E(|V|)</math> e <math>T_U(|V|)</math> sono le complessità necessarie alle operazioni di costruzioni di una coda con <math>|V|</math> elementi, estrazione del minimo da una coda con <math>|V|</math> elementi e la riduzione di un valore in una coda con <math>|V|</math> elementi.

Riga 103:

È interessante notare che, nel caso in cui il grafo '''non''' sia sufficientemente sparso e <math>|E| \in \Omega( |V|^2 / \log_2 |V| )</math>, la soluzione basata sugli array è più efficiente di quella implementata tramite le [[Heap binario|heap binarie]].

== Esempio ==

Alla base di questi problemi c'è lo scopo di trovare il percorso minimo (più corto, più veloce, più economico…) tra due punti, uno di partenza e uno di arrivo. Con il metodo che si vedrà è possibile ottenere non solo il percorso minimo tra un punto di partenza e uno di arrivo ma l'[[albero dei cammini minimi]], cioè tutti i percorsi minimi tra un punto di partenza e tutti gli altri punti della rete. Come per praticamente tutti i problemi riguardanti le reti la cosa migliore è fare una schematizzazione della situazione per risolvere l'esercizio più agevolmente e avere sempre a disposizione i dati necessari. Una buona schematizzazione per i problemi di percorso minimo deve includere tutti i possibili collegamenti tra i nodi (e i relativi costi) e deve essere fissato un nodo di partenza.

Con il metodo che vedremo è possibile ottenere non solo il percorso minimo tra un punto di partenza e uno di arrivo ma l'[[albero dei cammini minimi]], cioè tutti i percorsi minimi tra un punto di partenza e tutti gli altri punti della rete.

Come per praticamente tutti i problemi riguardanti le reti la cosa migliore è fare una schematizzazione della situazione in cui ci troviamo per risolvere l'esercizio più agevolmente e avere sempre a disposizione i dati necessari.

Una buona schematizzazione per i problemi di percorso minimo deve includere tutti i possibili collegamenti tra i nodi (e i relativi costi) e deve essere fissato un nodo di partenza.

ConsideriamoSi consideri un problema in cui si vuole calcolare il percorso minimo tra casa e il posto di lavoro. SchematizziamoSi schematizzino tutti i possibili percorsi e il relativo tempo di percorrenza (supponendo di voler calcolare il percorso più breve in fatto di tempo di percorrenza). I nodi A, B, C, D, E indicano le cittadine per cui è possibile passare. Ecco una schematizzazione della rete:

[[File:Ricerca operativa percorso minimo 01.gif|center]]

DobbiamoBisogna ora assegnare a ogni nodo un valore, che chiameremochiamato “potenziale”, seguendo alcune regole:

<div style="float:center; width:80%; padding:15px; background: #f5f8ff; border: 1px solid blue; margin-left:8px; margin-right:8px;margin-bottom:15px; text-align:left">

* Ogni nodo ha, all'inizio potenziale <math>+ \infty</math> (che indichiamo con “inf”);

Riga 122 ⟶ 120:

* Quando si aggiorna il potenziale di un nodo si lascia quello minore (essendo un problema di percorso minimo).

</div>

VediamoSi in praticaveda come si risolve questo esercizio nella pratica. Questa è la rete in cui sono indicati anche i potenziali:

[[File:Ricerca operativa percorso minimo 02.gif|center]]

Seguendo le regole appena fissate consideriamosi consideri il nodo con potenziale minore (“casa”) e lo rendiamosi renda definitivo (colorandolo di rosso) e aggiorniamosi aggiornino tutti i nodi adiacenti sommando l'attuale valore del potenziale (ovvero zero) al costo del percorso. AggiorniamoSi aggiornino i potenziali perché avevamosi aveva, nel caso di A, potenziale infinito mentre ora abbiamoil potenziale è 2. Ricordando che il potenziale minore è sempre preferibile. VediamoEcco come si è aggiornata la rete:

[[File:Ricerca operativa percorso minimo 03.gif|center]]

Bisogna ora considerare il nodo non definitivo (ovvero quelli scritti in nero) con potenziale minore (il nodo A). Lo si rende definitivo e si aggiornano i potenziali dei nodi adiacenti B e C. IndichiamoSi indichi con una freccia da dove proviene il potenziale dei nodi resi definitivi.

[[File:Ricerca operativa percorso minimo 04.gif|center]]

Il nodo con potenziale minore ora è C. lo si rende definitivo e si aggiornano quelli adiacenti.

[[File:Ricerca operativa percorso minimo 05.gif|center]]

Va notato come il nodo D abbia ora potenziale 6 in quanto 6 è minore di 8 e quindi lo si aggiorna. Se avessimosi avutoavesse ottenuto un valore maggiore di quello che già c'era losi avremmosarebbe lasciatodovuto lasciare invariato. Si renda definitivo il nodo D e si aggiorni il grafico:

Rendiamo definitivo il nodo D e aggiorniamo il grafico:

[[File:Ricerca operativa percorso minimo 06.gif|center]]

Il nodo con potenziale minore restante è B e lo si rende definitivo aggiornando di conseguenza il grafico: