Esercizi e sorgenti dei programmi
Cammini di costo minimo tra tutte le coppie di vertici di un grafo pesato
L'algoritmo di ALLPAIRSSHORTESTPATH 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. La pseudo-codifica dell'algoritmo è la seguente:
ALLPAIRSSHORTESTPATH(G)
- Input: Un grafo pesato G
- Output: La matrice D(i,j) dei costi dei cammini minimi per ciascuna coppia di vertici vi, vj ∈ V(G)
- per ogni i,j =1, 2, ..., n:
- se (vi,vj) ∈ E(G) allora L(1)(i,j) = W(i,j)
- altrimenti L(1)(i,j) = ∞
- fine-ciclo
- per k=2, 3, ..., n-1:
- per i=1, 2, ..., n:
- per j=1, 2, ..., n:
- L(k)(i,j) = ∞
- per h=1, 2, ..., n:
- L(k)(i,j) = min{ L(k)(i,j), L(k-1)(i,h) + W(h,j) }
- fine-ciclo
- fine-ciclo
- fine-ciclo
- fine-ciclo
La compilazione del programma richiede l'uso della libreria grafi.c.
/* ** allPairsShortestPath.c ** ** Implementazione di un algoritmo di programmazione dinamica per il ** calcolo del cammino di costo minimo tra ogni coppia di vertici di ** un grafo G con pesi assegnati agli spigoli. ** ** AllPairsShortestPath(G) ** INPUT: Un grafo G orientato con pesi W(u,v) assegnati agli spigoli ** OUTPUT: La matrice D dei costi dei cammini minimi per ciascuna coppia ** di vertici in V(G) ** per ogni i,j =1, 2, ..., n: ** se (i,j) e' uno spigolo di G allora L(1)(i,j) = W(i,j) ** altrimenti L(1)(i,j) = infinito ** fine-ciclo ** per k=2, 3, ..., n-1: ** per i=1, 2, ..., n: ** per j=1, 2, ..., n: ** L(k)(i,j) = infinito ** per h=1, 2, ..., n: ** L(k)(i,j) = min{L(k)(i,j), L(k-1)(i,h)+W(h,j)} ** fine-ciclo ** fine-ciclo ** fine-ciclo ** fine-ciclo ** ** #(@)20120429(liverani@mat.uniroma3.it) */ #include <stdlib.h> #include <stdio.h> #include <limits.h> #include "grafi.h" /* * Funzione che implementa l'algoritmo AllPairsShortestPath */ void allPairsShortestPath(grafoPesato G, int **D) { int ***L, i, j, k, h; /* allocazione dinamica della matrice L con 3 dimensioni */ L = malloc(sizeof(int *)*(G.n+1)); for (k=1; k<=G.n; k++) { L[k] = malloc(sizeof(int *)*(G.n+1)); for (i=1; i<=G.n; i++) { L[k][i] = malloc(sizeof(int)*(G.n+1)); } } /* inizializzazione di L */ for (i=1; i<=G.n; i++) for (j=1; j<=G.n; j++) L[1][i][j] = G.W[i][j]; /* allPairsShortestPath */ for (k=2; k<G.n; k++) { for (i=1; i<=G.n; i++) { for (j=1; j<=G.n; j++) { L[k][i][j] = INFINITO; for (h=1; h<=G.n; h++) { if (L[k][i][j] > L[k-1][i][h]+G.W[h][j]) { L[k][i][j] = L[k-1][i][h]+G.W[h][j]; } } } } } /* copia L[k] in D */ for (i=1; i<=G.n; i++) for (j=1; j<=G.n; j++) D[i][j] = L[G.n-1][i][j]; return; } /* * funzione principale */ int main(void) { grafoPesato G; int **D, i, j; leggiGrafoPesato(&G); D = malloc((G.n+1)*sizeof(int *)); for (i=1; i<=G.n; i++) D[i] = malloc((G.n+1)*sizeof(int)); allPairsShortestPath(G, D); printf("Matrice dei costi minimi:\n"); for (i=1; i<=G.n; i++) { for (j=1; j<=G.n; j++) if (D[i][j] < INFINITO) printf("%3d ", D[i][j]); else printf("INF "); printf("\n"); } return(0); }