Algoritmo di Dijkstra

1. Cos'è l'Algoritmo di Dijkstra?

L'algoritmo di Dijkstra è uno dei più importanti ed efficienti algoritmi nella teoria dei grafi. Sviluppato dall'informatico olandese Edsger W. Dijkstra nel 1959, risolve il problema del cammino minimo a sorgente singola (Single-Source Shortest Path) su un grafo orientato o non orientato i cui archi presentano pesi non negativi ($\ge 0$).

L'obiettivo è determinare la distanza minima dal nodo di partenza (sorgente) verso tutti gli altri vertici raggiungibili all'interno della struttura reticolare.

2. Meccanismo di Funzionamento e Codice C++

L'algoritmo adotta un approccio greedy (ingordo). Mantiene un vettore delle distanze provvisorie inizializzate a infinito ($\infty$) tranne per la sorgente posta a $0$, e utilizza una coda di priorità (`std::priority_queue`) per selezionare in modo efficiente il nodo non visitato con la distanza minima corrente.

                // Implementazione dell'Algoritmo di Dijkstra in C++
                #include <vector>
                #include <queue>
                #include <iostream>

                const int INF = 1e9;

                void dijkstra(int start, const std::vector<std::vector<std::pair<int, int>>>& adj,
                std::vector<int>& dist) {
                int n = adj.size();
                dist.assign(n, INF);

                // Min-heap che memorizza coppie: {distanza, nodo}
                std::priority_queue<std::pair<int, int>, std::vector<std::pair<int, int>>,
                std::greater<std::pair<int, int>>> pq;

                dist[start] = 0;
                pq.push({0, start});

                while (!pq.empty()) {
                int d = pq.top().first;
                int u = pq.top().second;
                pq.pop();

                if (d > dist[u]) continue;

                for (auto& edge : adj[u])
                {
                int v = edge.first;
                int weight = edge.second;

                // Rilassamento dell'arco (Relaxation)
                if (dist[u] + weight < dist[v]) {
                dist[v] = dist[u] + weight;
                pq.push({dist[v], v});
                }
                }
                }
                }
            

3. Analisi della Complessità

Complessità Temporale $\mathcal{O}((V + E) \log V)$: Utilizzando una coda di priorità basata su heap binario, ogni inserimento e rimozione richiede $\log V$ operazioni. $V$ è il numero di vertici ed $E$ il numero di archi.
Complessità Spaziale $\mathcal{O}(V + E)$: Necessaria per la memorizzazione della lista di adiacenza del grafo, del vettore delle distanze e dello stack della coda di priorità.

4. Simulatore Interattivo: Algoritmo di Dijkstra

Seleziona il nodo di partenza (da 0 a 4) per calcolare i cammini minimi su un grafo campione predefinito di prova.

dijkstra@nexus-core:~# Shortest Path Simulator

Nodo Sorgente Iniziale (0 - 4):

> Seleziona il nodo sorgente e avvia la simulazione per calcolare le distanze minime.

1. Cos'è l'Algoritmo di Dijkstra?

2. Meccanismo di Funzionamento e Codice C++

3. Analisi della Complessità

4. Simulatore Interattivo: Algoritmo di Dijkstra

Gestione della Privacy e dei Cookie