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)

  1. D(0) = W
  2. per ogni i = 1, 2, ..., n:
  3.    per ogni j = 1, 2, ..., n:
  4.      se i=j o W(i,j) = ∞)
  5.      allora π(0)(i,j) = null
  6.      altrimenti π(0)(i,j) = i
  7.    fine-ciclo
  8. fine-ciclo
  9. per k = 1, 2, ..., n:
  10.    per u = 1, 2, ..., n:
  11.      per v = 1, 2, ..., n:
  12.        T(k)(u,v) = T(k-1)(u,v) or (T(k-1)(u,k) and T(k-1)(k,v))
  13.        se D(k-1)(u,v) ≤ D(k-1)(u,k) + D(k-1)(k,v)
  14.        allora π(k)(u,v) = π(k-1)(u,v), D(k)(u,v) = D(k-1)(u,v)
  15.        altrimenti π(k)(u,v) = π(k-1)(k,v), D(k)(u,v) = D(k-1)(u,k) + D(k-1)(k,v)
  16.      fine-ciclo
  17.    fine-ciclo
  18. 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);
}