Esercizi e sorgenti dei programmi
Algoritmo di Floyd-Warshall
L'algoritmo FLOYDWARSHALL risolve il problema del cammino di costo minimo fra tutte le coppie di vertici di un grafo G con pesi assegnati agli spigoli, utilizzando la tecnica generale della programmazione dinamica. L'algoritmo presentato di seguito calcola il costo del cammino minimo tra ogni coppia di vertici del grafo, il cammino di costo minimo tra ogni coppia di vertici e la matrice di adiacenza del grafo “chiusura transitiva” del grafo G. La pseudo-codifica dell'algoritmo è la seguente:
FLOYDWARSHALL(G)
- Input: Un grafo pesato G
- Output: La matrice D dei costi dei cammini minimi per ciascuna coppia di vertici vi, vj ∈ V(G), la matrice π con il predecessore di ogni vertice nel cammino minimo tra ogni coppia di vertici del grafo e la matrice di adiacenza T del grafo chiusura transitiva di G
- D(0) = W
- per ogni i = 1, 2, ..., n:
- per ogni j = 1, 2, ..., n:
- se i=j o W(i,j) = ∞
- allora π(0)(i,j) = null
- altrimenti π(0)(i,j) = i
- fine-ciclo
- fine-ciclo
- per k = 1, 2, ..., n:
- per u = 1, 2, ..., n:
- per v = 1, 2, ..., n:
- T(k)(u,v) = T(k-1)(u,v) or (T(k-1)(u,k) and T(k-1)(k,v))
- se D(k-1)(u,v) ≤ D(k-1)(u,k) + D(k-1)(k,v)
- allora π(k)(u,v) = π(k-1)(u,v), D(k)(u,v) = D(k-1)(u,v)
- altrimenti π(k)(u,v) = π(k-1)(k,v), D(k)(u,v) = D(k-1)(u,k) + D(k-1)(k,v)
- fine-ciclo
- fine-ciclo
- fine-ciclo
La compilazione del programma richiede l'uso della libreria grafi.c.
/* ** floydWarshall.c ** ** Implementazione dell'algoritmo di Floyd-Warshall per il calcolo ** del cammino di costo minimo tra ogni coppia di vertici di un grafo G ** con pesi assegnati agli spigoli e della chiusura transitiva di G. ** ** FloydWarshall(G) ** INPUT: Un grafo G orientato con funzione peso w:E(G) --> R ** OUTPUT: La matrice D dei pesi dei cammini minimi per ciascuna ** coppia di vertici in V(G), la matrice Pi dei predecessori ** dei vertici di V(G) nei cammini minimi, la matrice di ** adiacenza T del grafo chiusura transitiva di G ** D(0) = W ** per u = 1, 2, ..., n: ** per v = 1, 2, ..., n: ** se u=v o W(u,v) = infinito ** allora Pi(0)(u,v) = null ** altrimenti Pi(0)(u,v) = u ** fine-ciclo ** fine-ciclo ** per k = 1, 2, ..., n: ** per u = 1, 2, ..., n: ** per v = 1, 2, ..., n: ** T(k)(u,v) = T(k-1)(u,v) or (T(k-1)(u,k) and T(k-1)(k,v)) ** se D(k-1)(u,v) <= D(k-1)(u,k) + D(k-1)(k,v) ** allora Pi(k)(u,v) = Pi(k-1)(u,v), D(k)(u,v) = D(k-1)(u,v) ** altrimenti Pi(k)(u,v) = Pi(k-1)(k,v), D(k)(u,v) = D(k-1)(u,k) + D(k-1)(k,v) ** fine-ciclo ** fine-ciclo ** fine-ciclo ** ** #(@)20120430(liverani@mat.uniroma3.it) */ #include <stdlib.h> #include <stdio.h> #include <limits.h> #include "grafi.h" /* * Funzione che implementa l'algoritmo di Floyd-Warshall */ void floydWarshall(grafoPesato G, int ***D, int ***Pi, int ***T) { int i, j, k; /* inizializzazione di D, Pi */ for (i=1; i<=G.n; i++) for (j=1; j<=G.n; j++) { D[0][i][j] = G.W[i][j]; if (i==j || G.W[i][j]==INFINITO) Pi[0][i][j] = -1; else Pi[0][i][j] = i; if (i==j || G.W[i][j]<INFINITO) T[0][i][j] = 1; else T[0][i][j] = 0; } /* corpo dell'algoritmo */ for (k=1; k<=G.n; k++) { for (i=1; i<=G.n; i++) { for (j=1; j<=G.n; j++) { T[k][i][j] = T[k-1][i][j] || (T[k-1][i][k] && T[k-1][k][j]); if (D[k-1][i][j] <= D[k-1][i][k] + D[k-1][k][j]) { Pi[k][i][j] = Pi[k-1][i][j]; D[k][i][j] = D[k-1][i][j]; } else { Pi[k][i][j] = Pi[k-1][k][j]; D[k][i][j] = D[k-1][i][k] + D[k-1][k][j]; } } } } return; } /* * funzione principale */ int main(void) { grafoPesato G; int ***D, ***Pi, ***T, i, j; leggiGrafoPesato(&G); /* allocazione dinamica delle matrici D, Pi, T */ D = malloc((G.n+1)*sizeof(int *)); Pi = malloc((G.n+1)*sizeof(int *)); T = malloc((G.n+1)*sizeof(int *)); for (i=0; i<=G.n; i++) { D[i] = malloc((G.n+1)*sizeof(int *)); Pi[i] = malloc((G.n+1)*sizeof(int *)); T[i] = malloc((G.n+1)*sizeof(int *)); for (j=0; j<=G.n; j++) { D[i][j] = malloc((G.n+1)*sizeof(int)); Pi[i][j] = malloc((G.n+1)*sizeof(int)); T[i][j] = malloc((G.n+1)*sizeof(int)); } } /* esecuzione dell'algoritmo di Floyd-Warshall */ floydWarshall(G, D, Pi, T); /* stampa dei risultati */ printf("Matrice dei costi dei cammini minimi:\n"); for (i=1; i<=G.n; i++) { for (j=1; j<=G.n; j++) if (D[G.n][i][j] < INFINITO) printf("%3d ", D[G.n][i][j]); else printf("INF "); printf("\n"); } printf("\nMatrice dei cammini minimi:\n"); for (i=1; i<=G.n; i++) { for (j=1; j<=G.n; j++) if (D[G.n][i][j] < INFINITO) printf("%3d ", Pi[G.n][i][j]); else printf("nil "); printf("\n"); } printf("\nMatrice di adiacenza della chiusura transitiva di G:\n"); for (i=1; i<=G.n; i++) { for (j=1; j<=G.n; j++) printf("%1d ", T[G.n][i][j]); printf("\n"); } return(0); }