La programmazione dinamica è una tecnica di risoluzione di problemi basata sulla divisione del problema in sottoproblemi più semplici e sulla memorizzazione delle soluzioni di questi sottoproblemi per evitare di doverli risolvere un altra volta. La programmazione dinamica è utilizzata in moltissimi ambiti tra cui la robotica, l'intelligenza artificiale, l'analisi di algoritmi ecc...
Come si può intuire questa tecnica viene usata per l'ottimizzazione quindi trovare la soluzione migliore a un problema tra molte possibili soluzioni, non proprio la cosa più semplice.
Un esempio banale di ottimizzazione è il problema dello zaino in cui è necessario scegliere oggetti con dimensioni e pesi diversi in modo da massimizzare il valore totale degli oggetti selezionati rispettando peso e spazio massimo occupabile.
In ambito programmazione un esempio lampante può essere quello di ricercare il cammino più breve tra due nodi in un grafo pesato, in questo caso si conta le distanze minime tra i nodi già visti e si utilizzano per calcolare le distanze dei nodi adiacenti.
L'algoritmo di Dijkstra è un algoritmo di ricerca di questi spazi minimi che trova il cammino più breve tra un nodo di partenza e tutti gli altri nodi in un grafo orientato e pesato.
Questo algoritmo funziona assegnando a ogni nodo un valore che rappresenta la distanza minima dal nodo di partenza, procedendo il loop in seguito conta il nodo con il valore di distanza minimo tra quelli non ancora visitati poi calcola le distanze dei nodi adiacenti al nodo selezionato.
N.B. L'algoritmo aggiorna il valore di distanza solo se la nuova distanza è minore della vecchia distanza, chiaramente viene ripetuto fino a quando tutti i nodi sono stati visitati.
Esempio di codice C++ che implementa l'algoritmo di Dijkstra:
#include <iostream>
#include <vector>
#include <queue>
#include <climits>
using namespace std;
typedef pair<int, int> pii;
typedef vector<vector<pii>> Graph;
void dijkstra(const Graph& graph, int start, vector<int>& dist) {
priority_queue<pii, vector<pii>, greater<pii>> pq;
pq.push({0, start});
dist[start] = 0;
while (!pq.empty()) {
int u = pq.top().second;
pq.pop();
for (const auto& edge : graph[u]) {
int v = edge.first;
int w = edge.second;
if (dist[v] > dist[u] + w) {
dist[v] = dist[u] + w;
pq.push({dist[v], v});
}
}
}
}
int main() {
int n, m;
cin >> n >> m;
Graph graph(n);
for (int i = 0; i < m; i++) {
int u, v, w;
cin >> u >> v >> w;
graph[u].push_back({v, w});
graph[v].push_back({u, w});
}
int start, end;
cin >> start >> end;
vector<int> dist(n, INT_MAX);
dijkstra(graph, start, dist);
cout << "Il cammino piu' breve da " << start << " a " << end << " e' " << dist[end] << endl;
return 0;
}L'algoritmo di Dijkstra a lato pratico può essere utilizzato in molti ambiti come ad esempio la progettazione di reti di comunicazione (calcolando il percorso più breve tra i nodi di una rete per minimizzare i ritardi di trasmissione), la creazione di mappe stradali, la ricerca di percorsi in giochi di strategia ecc...
