Programmazione dinamica, algoritmo di Dijkstra C++!

Samueleex

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

Giulio_M

Samueleex con un po' di ritardo, ho trovato un confronto interessante: l'algoritmo di Dijkstra con l'algoritmo A*. Più diffuso il primo e generalmente più utilizzato, in generale però può essere più conveniente valutare prima se usare una o l'altra soluzione. Per la tipologia di funzionamento, abbiamo:

Dijikstra si presta meglio (ovvero è più efficiente) ad un grafo senza ostacoli: visita tutti i nodi per trovare il percorso più breve fra due punti
A* è invece più efficiente in un grafo con ostacoli: oltre a considerare il costo fra il nodo di partenza e quello di destinazione, determina una funzione di valutazione per scegliere quale nodo esplorare successivamente, tramite una stima di quello che verrà dopo (infatti non può che essere una stima) ovvero minimizzare tale funzione, scegliere i nodi che secondo le stime sono più promettenti per raggiungere la destinazione, con un costo computazionale inferiore

Giulio_M

L'algoritmo di Dijkstra è stato ora dimostrato essere efficiente e anche "universalmente ottimale"

Sviluppato da Edsger Dijkstra nel 1956 e pubblicato nel 1959, l'omonimo algoritmo nel corso della storia è sempre stato uno degli algoritmi più studiati, quando si tratta di cercare il cammino minimo (minizzare la somma dei costi) in un grafo, con o senza ordinamento. Le ripercussioni pratiche ovviamente sono enormi, pensiamo in generale al trasporto, sistemi complessi come chiusure stradali, traffico, oltre alla sola distanza, lineare o vincolata, fra due punti. Come detto l'algoritmo di Dijkstra era sicuramente uno dei più noti e diffusi, mancava però uno studio approfondito che lo definisse "il migliore" in tutte le situazioni.

Di recente (18 ottobre 2024) il ricercatore Václav Rozhoň del Politecnico federale di Zurigo (ETH Zurich) ha pubblicato su arxiv.org il paper ufficiale intitolato <<Instance-Optimality in I/O-Efficient Sampling and Sequential Estimation>>, in cui fondamentalmente dimostra che una variante dell'algoritmo di Dijkstra è universalmente ottimale per il problema del percorso più breve da un singolo punto di partenza. Nello specifico, una particolare struttura dati (heap) che consente di accedere rapidamente agli elementi più recenti e questa struttura dati, combinata con l'algoritmo di Dijkstra, permette di ottenere prestazioni migliori rispetto ad altre soluzioni.

Anche se non sono sempre ben chiare le possibili applicazioni immediate del nuovo algoritmo, della nuova variante, lo sviluppo di metodi numerici e teorici è sempre un forte strumento che potrà trovare applicazione in futuro (ad esempio, l'analisi numerica e relativi metodi risolutivi, sono nati concettualmente ben prima dei computer).

Questo risultato, dimostra appunto che la variante dell'algoritmo di Dijkstra ad oggi è "universalmente ottimale", ciò non toglie possibilità che in futuro, altri algoritmi riescano a determinare ottimalità anche più forti, ideali per altri problemi applicativi.

Un approfondimento in lingua inglese lo troviamo qui: quantamagazine.org. Dallo stesso sito, una raffigurazione concettuale della variante modificata dell'algoritmo di Dijkstra.

variante algoritmo di Dijkstra - universalmente ottimale (fonte immagine: quantamagazine.org)

Fondatori