2023-12-21 - APSP

universityin-classsubject-2101

2023-12-21

Algoritmi

APSP

All Pairs Shortest Path
Indica il problema del calcolo del cammino minimo tra tutte le coppie di nodi.

In SSSP utilizzavamo per contenere il cammino minimo attuale dal nodo al nodo . Qui è necessario cambiare la sorgente, quindi si utilizza una matrice bidimensionale.
indica il cammino minimo attuale da a .
Invece di e si utilizzano, per convenzione, e .

L’obiettivo è ottenere .

Per questo tipo di problemi conviene sempre utilizzare la matrice di adiacenza per rappresentare il grafo. Il vantaggio di efficienza delle liste viene perso dovendo utilizzare .

Rappresentazione di un grafo direzionale tramite matrice

Si ricorda che per rappresentare un grafo non pesato direzionale, si utilizza una matrice dove in ogni cella è presente se è presente un arco che va da a (rispettivamente da numero di riga verso numero di colonna ), altrimenti .

Per i grafi pesati al posto di si mette il peso dell’arco, e al posto di si mette (come se l’arco esistesse ma con un peso infinito). Nella diagonale principale sarà presente il peso dell’arco che va da un nodo verso se stesso. Sarà quindi presente in tutte le celle della diagonale principale ()

La matrice conterrà in tutte le celle della diagonale principale. Ogni nodo per raggiungere se stesso ha un . Quindi

Nota: Se il grafo dovesse contenere cicli con peso negativo quanto descritto precedentemente non varrebbe più, e il problema non sarebbe risolvibile.

Algoritmo con SSSP

Avendo già visto come risolvere il problema di SSSP. sarebbe sufficiente effettuare iterazioni di algoritmi SSSP e si risolverebbe il problema.
La complessità sarebbe quindi quella dell’algoritmo SSSP utilizzato, moltiplicata per . Quindi:

• BF:
• DAG:
• DIJ:

Non è il modo più efficiente di risolvere il problema.

Il problema di SSSP gode della proprietà della sottostruttura ottima e quindi utilizzando sotto problemi ottimali arriva a risolvere il problema principale. Vengono quindi calcolati tutti i sottocammini minimi da ogni nodo del cammino minimo principale verso il nodo finale.

Ad esempio, calcolare con SSSP, consente anche di trovare , e .

graph LR;
u((u))-->v1((v1))
v1-->v2((v2))
v2-->v3((v3))
v3-->v((v))

Si sfrutta la programmazione dinamica.

Indichiamo con la lunghezza massima di un cammino minimo.
Indichiamo con il cammino minimo da a di lunghezza al massimo .
In tutti i grafi vale

in quanto in un cammino minimo non può essere più lungo di archi (stesso ragionamento utilizzato in Bellman Ford). Se si ottiene un cammino minimo inferiore anche un numero di archi superiore, vuol dire che sono presenti cicli con peso negativo.

dove è la matrice che rappresenta i pesi del grafo (e quindi il grafo vero e proprio).

Caso Base:

• si potrebbe prendere . In questo caso , altrimenti .
• si prende invece considerando che coincide con la matrice del grafo iniziale.
  Passo Induttivo: si ottiene a partire da . Quindi .

Per passare da a è sufficiente aggiungere un arco. Il ragionamento è analogo a quello fatto per la RELAX:

Nel calcolo del minimo più interno della formula , si può evitare di controllare il caso in cui . Coinciderebbe con il dover calcolare (che è calcolato esternamente).

n = |V|

EXTEND-SHORTEST-PATH(Dn_1, w):
	Dn = MATRIX(n x n)
	FOR i=1 TO n DO:
		FOR j=1 TO n DO:
			Dn[i,j] = +INF
			FOR k=1 TO n DO:
				Dn[i,j] = min(Dn[i,j], Dn_1[i,k]+w(k, j))
	RETURN Dn;

APSP(w, n):
	D1 = w
	FOR m=2 TO n:
		Dm = EXTEND-SHORTEST-PATH(Dm_1, w)
	// si potrebbe controllare che non siano presenti cicli con peso negativo come fatto con BF.
	RETURN D

La complessità è , uguale a quella ottenuta dall’iterazione dell’algoritmo di BF.

L’algoritmo sopra citato viene chiamato anche come metodo della moltiplicazione di matrici.

MATRIX-MULTIPLY(A, B):
	C = MATRIX(n x n)
	FOR i=1 TO n DO:
		FOR j=1 TO n DO:
			C[i,j]=0
			FOR k=1 TO n DO:
				C[i, j] += A[i,k] + B[k, j]

Questo algoritmo che effettua la moltiplicazione tra due matrici è molto simile a quello di EXTEND-SHORTEST-PATH.

Con l’algoritmo calcoleremo come segue:

Di fatto è come scrivere . Vale quindi la proprietà della somma degli esponenti (come avviene per il prodotto di potenze).
Per calcolare è sufficiente calcolare e moltiplicare la matrice per se stessa. .
L’algoritmo a questo punto diventa logaritmico .

FAST-APSP(w)
	D1 = w
	m = 1
	WHILE (m < n-1) DO
		D^2m = EXTEND-SHORTEST-PATH(D^m, D^m)
		m = 2m
	RETURN D^m

Se per calcolare arriverei (moltiplicando per due) a ().
Se non esistono cicli di peso negativo, .

Possibile domanda

Scrivere la definizione ricorsiva del calcolo di una soluzione ottima dell’algoritmo FAST-APSP.
.

Possibile domanda

Scrivere la definizione ricorsiva del calcolo di una soluzione ottima dell’algoritmo APSP.
.