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 v_i, v_j ∈ V(G)

1. per ogni i,j =1, 2, ..., n:
2.    se (v_i,v_j) ∈ E(G) allora L⁽¹⁾(i,j) = W(i,j)
3.    altrimenti L⁽¹⁾(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);
}