Cammini Minimi in Grafi Pesati e Dijkstra

L'algoritmo Dijkstra è un algoritmo che trova il percorso più breve da un vertice sorgente a tutti gli altri vertici in un grafo pesato.

L'attributo v.d rappresenta la distanza stimata del vertice v dal nodo sorgente. Inizialmente, la distanza di v dal nodo sorgente è infinita se v non è il nodo sorgente.

L'algoritmo di Dijkstra costruisce un albero radicato nel nodo sorgente, aggiungendo un vertice alla volta. Questo albero memorizza implicitamente i cammini trovati dall'algoritmo.

Quando un vertice u viene inserito nell'albero, l'algoritmo aggiorna le distanze stimate dei vertici adiacenti a u. Questa operazione serve a trovare potenziali nuovi cammini più brevi.

L'algoritmo Dijkstra trova il percorso più breve da un nodo sorgente a tutti gli altri nodi in un grafo pesato. Il risultato è un insieme di distanze dai nodi sorgente a tutti gli altri nodi.

Nel contesto del grafico presentato, "d" rappresenta la distanza di un nodo dall'origine. Quindi, A.d=0 significa che il nodo A è l'origine e ha una distanza di 0 da se stesso.

Ogni nodo, tranne l'origine, ha una distanza (d) che indica la distanza dal nodo di partenza. Questa distanza viene calcolata durante il processo di attraversamento del grafico.

Il nodo scelto per l'attraversamento del grafico, che influenzerà il calcolo delle distanze.

Il processo di attraversamento del grafico coinvolge l'esplorazione di tutti i nodi, a partire dal nodo scelto. Questo processo può coinvolgere l'individuazione di diversi percorsi possibili.

L'algoritmo descritto non funziona con pesi negativi. Questo significa che i pesi dei collegamenti tra i nodi non possono essere negativi, poiché potrebbe portare a risultati imprecisi o non validi.

L'invariante del ciclo descrive la condizione che rimane vera ad ogni iterazione del ciclo. Nel contesto dell'algoritmo di BFS, l'invariante indica che per ogni vertice t nel set Q, la distanza t.d rappresenta la distanza minima dal vertice sorgente s al vertice t.

La dimostrazione della correttezza dell'algoritmo di BFS si basa sul principio dell'induzione. Si dimostra che l'invariante del ciclo è vero all'inizio, si ipotizza che sia vero alla fine della fase di costruzione parziale dell'albero e si dimostra che rimane vero all'aggiunta del nuovo vertice u.

Il set Q rappresenta l'insieme dei nodi che devono ancora essere esplorati durante l'algoritmo di BFS. Contiene i nodi che sono stati visitati ma i cui vicini non sono ancora stati analizzati.

L'algoritmo Breadth-First Search (BFS) è un algoritmo di ricerca grafica che esplora sistematicamente un grafo in livelli, a partire da un nodo sorgente s, trovando tutti i nodi con la distanza minima da s.

La funzione δ(s, t) rappresenta la distanza minima dal vertice sorgente s al vertice t. Questo valore viene aggiornato durante l'esecuzione dell'algoritmo di BFS.

Un sottocammino di un cammino minimo è esso stesso un cammino minimo.

Un sottocammino minimo di un cammino minimo è sempre minimo.

Durante l'esecuzione dell'algoritmo di Dijkstra, il valore della distanza di un vertice non in Q (non visitato) non viene aggiornato.

Durante l'esecuzione dell'algoritmo di Dijkstra, se un vertice v in Q (visitato) ha un predecessore (v.π) diverso da nil, allora il predecessore è anch'esso in Q.

Durante l'esecuzione dell'algoritmo di Dijkstra, un vertice v ha una distanza finita (v.d ≠ ∞) se e solo se ha un predecessore (v.π) ≠ nil.

Durante l'esecuzione dell'algoritmo di Dijkstra, se un vertice v ha una distanza finita (v.d ≠ ∞), questa distanza è uguale alla distanza del suo predecessore (v.π) più il peso dell'arco che li collega.

Le proprietà invarianti del ciclo garantiscono la correttezza dell'algoritmo di Dijkstra.

Le proprietà invarianti del ciclo sono facilmente verificabili esaminando il ciclo di esecuzione dell'algoritmo.

Il valore dell'algoritmo di Dijkstra per il nodo u, definito come la somma del peso del cammino minimo da s a u.

Se il cammino tra s e u è minimo, allora anche il cammino tra s e y è minimo (proprietà 1) e y.d è uguale alla distanza minima tra s e y (δ(s, y)).

Il peso del cammino s → y è il peso del cammino s → x sull'arco (x, y) + il peso del cammino y → u. Quindi il peso totale del cammino s → u è y.d + W(y → u).

Il peso del cammino s → u è maggiore o uguale a y.d, che a sua volta è maggiore o uguale a u.d poiché u è un nodo esterno a Q. Questo dimostra che u.d rappresenta la distanza minima tra s e u.

La distanza minima tra due vertici, s e u, in un grafo pesato

Il set di vertici che sono stati visitati dall'algoritmo di Dijkstra.

Il peso di un arco (x, y) tra due nodi

L'invariante del ciclo è una condizione che rimane vera ad ogni iterazione del ciclo. In questo caso, l'invariante è che, per ogni vertice v che non fa parte della coda Q, la distanza v.d è infinita se e solo se esiste un cammino da s a v nel grafo G. Questa condizione è vera all'inizio dell'algoritmo e viene mantenuta ad ogni iterazione del ciclo.

La dimostrazione dell'invariante del ciclo prevede due parti: l'inizializzazione e il mantenimento. L'inizializzazione dimostra che l'invariante è vera all'inizio del ciclo. Il mantenimento dimostra che, se l'invariante è vera all'inizio di un'iterazione, rimane vera anche alla fine.

L'inizializzazione dell'invariante del ciclo dimostra che la condizione è vera all'inizio del ciclo. In questo caso, la coda Q contiene tutti i vertici del grafo G e la distanza di ogni vertice è infinita. Quindi, l'invariante è vera all'inizio perché, all'inizio, non ci sono cammini definiti e la distanza è infinita.

Il mantenimento dell'invariante del ciclo dimostra che, se l'invariante è vera all'inizio di un'iterazione, rimane vera anche alla fine. In questo caso, per dimostrare il mantenimento, si suppone che l'invariante sia vera all'inizio di un'iterazione e si dimostra che la condizione rimane vera dopo che un vertice u viene estratto dalla coda Q.

Se il vertice u viene estratto dalla coda Q con distanza infinita, allora tutti i vertici t che rimangono nella coda hanno una distanza infinita. Questo perché, se u aveva distanza infinita, non esisteva un cammino da s a u. Quindi, non esiste un cammino da s a nessun altro vertice t che rimane nella coda.

Se il vertice u viene estratto dalla coda Q con distanza finita, significa che esiste un cammino da s a u. Questo cammino è definito dall'antecessore di u, ovvero u.π. L'arco (u.π, u) è l'arco che collega il predecessore di u a u stesso.

Se il vertice u viene estratto dalla coda Q con distanza finita, il cammino da s a u è composto dal cammino da s a u.π (l'antecessore di u) più l'arco (u.π, u). In altre parole, per arrivare a u, si segue il cammino da s a u.π e poi si aggiunge l'arco che collega u.π a u.

Il fatto che il vertice u venga estratto dalla coda Q con distanza infinita è un assurdo perché s.d=0, ovvero la distanza da s a se stesso è 0. Quindi, non può esistere un vertice u con distanza infinita che venga estratto dalla coda. Questo dimostra che l'algoritmo è corretto e che, se un vertice viene estratto dalla coda, la sua distanza è necessariamente finita.