Esercizi e sorgenti dei programmi

Cammini di costo minimo tra tutte le coppie di vertici di un grafo pesato

L'algoritmo FASTALLPAIRSSHORTESTPATH 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:

FASTALLPAIRSSHORTESTPATH(G)

  1. per ogni i,j =1, 2, ..., n:
  2.    se (vi,vj) ∈ E(G) allora L(1)(i,j) = W(i,j)
  3.    altrimenti L(1)(i,j) = ∞
  4. fine-ciclo
  5. k=1
  6. fintanto che k<n-1:
  7.    per i=1, 2, ..., n:
  8.      per j=1, 2, ..., n:
  9.        L(2k)(i,j) = ∞
  10.        per h=1, 2, ..., n:
  11.          L(2k)(i,j) = min{ L(2k)(i,j), L(k)(i,h) + L(k)(h,j) }
  12.        fine-ciclo
  13.      fine-ciclo
  14.    fine-ciclo
  15.    k = 2k
  16. fine-ciclo

La compilazione del programma richiede l'uso della libreria grafi.c.

/*
**  fastAllPairsShortestPath.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.
**
**  FastAllPairsShortestPath(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
**    k = 1
**    fintanto che k < n-1:
**      per i=1, 2, ..., n:
**        per j=1, 2, ..., n:
**          L(2k)(i,j) = infinito
**          per h=1, 2, ..., n:
**            L(2k)(i,j) = min{L(2k)(i,j), L(k)(i,h)+L(k)(h,j)}
**          fine-ciclo
**        fine-ciclo
**      fine-ciclo
**      k = 2k
**    fine-ciclo
**
**  #(@)20120430(liverani@mat.uniroma3.it)
*/

#include <stdlib.h>
#include <stdio.h>
#include <limits.h>
#include "grafi.h"

/*
 *  Funzione che implementa l'algoritmo FastAllPairsShortestPath
 */

void fastAllPairsShortestPath(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<=2*G.n; k=k*2) {
    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];
  /* FastAllPairsShortestPath */
  k = 1;
  while (k < G.n-1) {
    for (i=1; i<=G.n; i++) {
      for (j=1; j<=G.n; j++) {
        L[2*k][i][j] = INFINITO;
        for (h=1; h<=G.n; h++) {
          if (L[2*k][i][j] > L[k][i][h]+L[k][h][j]) {
            L[2*k][i][j] = L[k][i][h]+L[k][h][j];
          }
        }
      }
    }
    k = 2*k;
  }
  /* copia L[k] in D */
  for (i=1; i<=G.n; i++)
    for (j=1; j<=G.n; j++) 
      D[i][j] = L[k/2][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));
  fastAllPairsShortestPath(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);
}