Soluzione: Algoritmo di Dijkstra
Complessità: Dipende dall'implementazione della coda di minima priorità (si veda [4]). In questo caso, per non complicare inutilmente il codice, si aggira completamente il problema usando semplicemente un array che porta ad un tempo totale $O(V^2)$
Il problema, e quindi anche la sua soluzione, è simile a quello che si cerca di risolvere nella Ricerca in Ampiezza (si veda [3]). La differenza è che qui il grafo è pesato ed orientato. L'algoritmo di Dijkstra tiene conto di questo iterando su tutti i vertici del grafo in maniera mirata assumendo l'invariante che, ad ogni ciclo, se si sceglie di processare il vertice che ha distanza minore dal vertice sorgente allora si è certi che quel vertice avrà distanza minima dalla sorgente (può sembrare una considerazione abbastanza banale ma è intorno a questa invariante che si costruirà l'algoritmo). Alla luce di questa considerazione, sarà utile conservare i vertici in una coda di minima priorità che mantenga gli stessi ordinati in maniera crescente in base alla loro distanza dalla sorgente.
Si prenda come esempio il grafo illustrato nell'immagine sopra (si veda [2] per ulteriori info sulla rappresentazione dei grafi) ed i passaggi illustrati nell'immagine sotto.
Prima della prima iterazione tutte le distanze dei vertici vengono impostate ad un valore molto grande (come $-1$ assegnato ad una variabile unsigned) tranne che per il vertice sorgente (il vertice $1$ in questo caso) a cui viene assegnato $0$. Ecco che l'invariante è valida prima di entrare nella prima iterazione. Infatti, scegliendo come primo vertice da processare il vertice sorgente (vertice $1$), che ha distanza $0$ da se stesso, si sceglie banalmente un vertice che ha distanza minima da quello sorgente.
Alla prima iterazione, dunque, (immagine A) si estrae dalla coda di minima priorità (si veda [4]) il vertice di testa (vertice sorgente in questo caso) che ha distanza sia minore che minima dalla sorgente (proprietà intrinseca del vertice sorgente) e si passa a processare tutti i vertici collegati al vertice scelto. Per ogni vertice $v$ collegato al vertice scelto $u$, se $v.\!distance > u.\!distance + peso(u, v)$ allora si può impostare $v.\!distance = u.\!distance + peso(u, v)$ dato che siamo sicuri che, grazie all'invariante, $u$ ha distanza minima dalla sorgente e che per trovare un cammino minimo dalla sorgente a $v$ basta sommare la distanza di $u$ dalla sorgente al peso dell'arco $u \longrightarrow v$.
Prima della seconda iterazione (immagine B) l'invariante deve essere ancora valida. Se si scegliesse, sbagliando, il vertice $2$, che ha distanza $6$, al posto del vertice $5$ che è ha distanza minore dalla sorgente, non esisterebbe mai nessun valore positivo dell'arco $2 \longrightarrow 5$ (che porta da vertice $2$ al vertice $5$) in grado di diminuire la distanza del vertice $5$ dalla sorgente (che quindi è già minima). Al contrario, scegliendo, giustamente, il vertice $5$ che ha distanza minore dalla sorgente, è possibile che l'arco $5 \longrightarrow 2$ (che porta dal vertice $5$ al vertice $2$) abbia un valore tale da risultare più conveniente nel cammino che inizia dalla sorgente (il vertice $1$) e passa per il vertice $2$. Questo significa che scegliendo il vertice $5$ l'invariante è ancora valida.
Le stesse operazioni si ripetono per tutte le iterazioni, finché non ci sono più elementi nella coda di priorità minima.
Per quanto riguarda il codice sorgente, per non complicare inutilmente le cose, si è optato per l'uso di un semplice array al posta di una coda di priorità minima. L'elemento $i$-esimo dell'array conterrà la distanza dell' $i$-esimo vertice del grafo. Per selezionare il vertice con distanza minima si itera su tutti gli elementi dell'array per trovare quello con valore minimo e se ne ritorna l'indice. Una volta "estratto", il vertice deve essere in qualche modo eliminato dal processo di selezione. Per questo, basta reimpostare il relativo l'elemento nell'array, che mantiene la distanza dalla sorgente, ad un valore molto grande, come $-1$.
#include <iostream> #include <queue> #include <vector> struct Vertex { Vertex *parent; unsigned int distance; unsigned int index; }; struct Edge { Vertex *head; Vertex *tail; Edge *next; unsigned int weight; }; void dijkstra(Edge**, Vertex*, size_t); size_t extract_min(unsigned int*, size_t); void relax(Edge*, unsigned int*); void print_path(Edge**, Vertex*, Vertex*, size_t); int main(int argc, char* argv[], char* env[]) { Vertex v1{ nullptr, (unsigned int)-1, 1 }; Vertex v2{ nullptr, (unsigned int)-1, 2 }; Vertex v3{ nullptr, (unsigned int)-1, 3 }; Vertex v4{ nullptr, (unsigned int)-1, 4 }; Vertex v5{ nullptr, (unsigned int)-1, 5 }; Vertex v6{ nullptr, (unsigned int)-1, 6 }; Vertex *v[7] = { nullptr, &v1, &v2, &v3, &v4, &v5, &v6 }; Edge *graph[7] = { nullptr }; Edge e1_25{ v[1], v[5], nullptr, 3 }; Edge e1_12{ v[1], v[2], &e1_25, 6 }; graph[1] = &e1_12; Edge e2_53{ v[2], v[3], nullptr, 3 }; Edge e2_25{ v[2], v[5], &e2_53, 1 }; graph[2] = &e2_25; Edge e3_34{ v[3], v[4], nullptr, 5 }; graph[3] = &e3_34; Edge e4_46{ v[4], v[6], nullptr, 1 }; graph[4] = &e4_46; Edge e5_36{ v[5], v[6], nullptr, 6 }; Edge e5_23{ v[5], v[3], &e5_36, 7 }; Edge e5_52{ v[5], v[2], &e5_23, 2 }; graph[5] = &e5_52; Edge e6_64{ v[6], v[4], nullptr, 2 }; graph[6] = &e6_64; size_t size = sizeof(v) / sizeof(Vertex*); dijkstra(graph, v[1], size); print_path(graph, v[1], v[4], v[4]->index); return 0; } void dijkstra(Edge **g, Vertex *v, size_t size) { v->distance = 0; std::queue<Vertex*> v_queue; std::vector<unsigned int> arr_distance(size); for (size_t i = 0; i < size; ++i) { if (i == v->index) arr_distance[i] = v->distance; else arr_distance[i] = (unsigned)-1; } while (v_queue.size() != (size - 1)) { size_t index = extract_min(arr_distance.data(), size); arr_distance[index] = (unsigned)-1; Edge *e = g[index]; v = e->head; v_queue.push(v); while (e != nullptr) { relax(e, arr_distance.data()); e = e->next; } } } size_t extract_min(unsigned int *arr_distance, size_t size) { size_t min_index, min = (unsigned)-1; for (size_t i = 0; i < size; ++i) { if (arr_distance[i] < min) { min = arr_distance[i]; min_index = i; } } return min_index; } void relax(Edge* e, unsigned int* arr_distance) { if (e->tail->distance > (e->head->distance + e->weight)) { e->tail->distance = e->head->distance + e->weight; e->tail->parent = e->head; arr_distance[e->tail->index] = e->tail->distance; } } void print_path(Edge **g, Vertex *s, Vertex *t, size_t index) { if (t == s) std::cout << s->index << " --> "; else if (t->parent == nullptr) std::cout << "No path between vertices."; else { print_path(g, s, t->parent, index); std::cout << t->index << ((t->index != index) ? " --> " : ""); } }
Riferimenti:
[1] Introduzione agli algoritmi e strutture dati - Cormen, Leiserson, Rivest, Stein
[2] Rappresentazione dei grafi attraverso strutture dati
[3] Grafi: Ricerca in Ampiezza
[4] Ordinamento: Heap Sort
Nessun commento:
Posta un commento