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)

  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. per k=2, 3, ..., n-1:
  6.    per i=1, 2, ..., n:
  7.      per j=1, 2, ..., n:
  8.        L(k)(i,j) = ∞
  9.        per h=1, 2, ..., n:
  10.          L(k)(i,j) = min{ L(k)(i,j), L(k-1)(i,h) + W(h,j) }
  11.        fine-ciclo
  12.      fine-ciclo
  13.    fine-ciclo
  14. 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);
}