This is lecture’s content for Bachelor’s degree in Computer Science and Management. These are exercises on shortest path problem.
Exercise 1#
Consider the oriented graph \(G = (V, E)\) and notice that it is connected with positive edges only:
It is required to manually apply Dijkstra algorithm to compute a shortest path tree starting from s. Show the final result adding for each node the minimum distance from s, highlighting the edges that leads to the shortest path.
Solution#
Exercise 2#
A road network is described using a oriented and weighted graph \(G = (V, E, w)\). For each edge \((u, v)\) the function \(w(u, v)\) models the amount of gas (in liters) to go from \(u \ \text{to} \ v\) and it always returns a positive number. A veichle can store up to \(C\) liters of gas in its tank and starts full. There are no gas stations along the way. It is required to write an efficient algorithm that takes \(G, C, s, d\), respectively the graph, the gas capacity and two nodes \(s, d\) and returns true if and only if exists a shortest path from \(d \ \text{to} \ s\) without emptying the tank.
Soluzione#
È sufficiente eseguire l’algoritmo di Dijkstra e calcolare il vettore D[v] delle distanze minime dalla sorgente s a ogni nodo v raggiungibile da s, utilizzando il consumo di carburante come peso. È possibile interrompere l’esecuzione dell’algoritmo di Dijkstra appena si raggiunge d oppure si supera il costo C. L’algoritmo restituisce true se e solo se si raggiunge d e non si è superato C.
Esercizio 3#
Si consideri un grafo orientato pesato, composto dai nodi {A, B, C, D, E}, la cui matrice di adiacenza è la seguente (le caselle vuote indicano l’assenza dell’arco corrispondente; l’intestazione di ogni riga indica il nodo sorgente, mentre l’intestazione della colonna indica il nodo destinazione):
- Disegnare il grafo corrispondente alla matrice di adiacenza.
- Determinare la distanza minima di ciascun nodo dal nodo sorgente A. Quale degli algoritmi visti a lezione può essere impiegato?
Soluzione#
Si nota come l’arco (D, C) abbia peso negativo; quindi per calcolare le distanze minime non è possibile usare l’algoritmo di Dijkstra, e si deve ricorrere ad esempio all’algoritmo di Bellman-Ford. Le iterazioni dell’algoritmo sono indicate nel seguito (i nodi in grigio sono quelli la cui distanza cambia):
Esercizio 4#
Consideriamo un grafo orientato G = (V, E) i cui archi abbiano pesi non negativi. Denotiamo con w(u, v) il peso dell’arco orientato (u, v). Ricordiamo che l’algoritmo di Dijkstra per il calcolo dei cammini minimi da una singola sorgente s ha la seguente struttura generica:
Tree DIJKSTRAGENERICO( grafo G = (V, E), nodo s )
inizializza D tale che D[s] = 0 e D[v] = +∞ per ogni v ≠ s;
T ← albero formato dal solo vertice s;
while ( T ha meno di n nodi ) do
trova l'arco (u,v) incidente su T con D[u] + w(u,v) minimo;
D[v] ← D[u] + w(u,v);
rendi u padre di v in T;
end while
return T;
Scrivere una versione dell’algoritmo di Dijkstra che non faccia uso di una coda di priorità ma di una semplice lista, in modo che ad ogni passo esamini sistematicamente gli archi incidenti per individuare quello che minimizza la distanza.
Determinare il costo computazionale della variante dell’algoritmo di Dijkstra descritta al punto 1. Specificare quale struttura dati viene usata per rappresentare il grafo.
Soluzione#
Supponiamo che, per ogni vertice v, la distanza tra la sorgente s e v sia indicata con l’attributo v.d; possiamo quindi scrivere la variante dell’algoritmo di Dijkstra come segue:
Tree DIJKSTRACONLISTE( grafo G=(V, E, w), nodo s )
foreach v in V do
v.d := +∞
endfor
s.d := 0; // il nodo sorgente ha distanza zero da se stesso
T := albero formato dal solo vertice s
Lista L;
L.INSERT(s); // inserisci s in L
while ( ! L.ISEMPTY() ) do
sia u il nodo di L con minimo valore u.d // costo: O(n) nel caso peggiore
rimuovi u da L // costo: O(1) se L è una lista doppiamente concatenata
foreach (u, v) in E do
if(v.d == +∞) then
v.d := u.d + w(u,v);
rendi u padre di v in T;
L.INSERT(v); // v non era nella lista, inseriscilo. Costo O(1)
elseif (u.d + w(u,v) < v.d) then
v.d := u.d + w(u,v);
rendi u nuovo padre di v in T;
// v era già nella lista, non va reinserito
endif
endfor
endwhile
return T;
Si noti che l’algoritmo DIJKSTRACONLISTE è leggermente più semplice da descrivere rispetto all’algoritmo di Dijkstra implementato con code di priorità visto a lezione. Infatti nel caso in cui u.d + w(u, v) < v.d, cioè nel caso in cui abbiamo scoperto un cammino più breve tra s e v che passa attraverso il nodo u, il nodo v non va reinserito nella struttura dati (nel nostro caso la lista), perché sicuramente vi è già contenuto.
Il costo di DIJKSTRACONLISTE è O(n^2), essendo n il numero di nodi del grafo. Notiamo infatti quanto segue:
Il ciclo while viene eseguito al più n volte. Questo perché ad ogni iterazione viene estratto un nodo dalla lista, e una volta estratto un nodo questo non viene più reinserito (questo è lo stesso ragionamento che abbiamo fatto per calcolare il costo computazionale dell’algoritmo di Dijkstra implementato tramite coda di priorità);
Ogni singola operazione di ricerca del nodo u tale che u.d sia minimo ha costo O(n). Infatti la lista L conterrà al più n nodi (in quanto il grafo ha n nodi) e va scansionata per intero, dato che non è mantenuta in alcun ordina particolare. Dato che questa operazione viene eseguita una volta per ciascuno degli n nodi estratti dalla lista (vedi punto precedente), il costo complessivo è O(n^2);
Il corpo del ciclo foreach viene eseguito in tutto O(m) volte durante l’intera esecuzione dell’algoritmo. Notiamo infatti che ogni arco del grafo viene visitato esattamente una volta.
Combinando quanto sopra, il costo dell’algoritmo è O(n^2) + O(m) = O(n^2), dato che in un grafo si ha sempre m = O(n^2) (perché il massimo numero di archi di un grafo orientato è n(n - 1) ).
By Jocelyne Elias and Moreno Marzolla