Gli esercizi

Testi e soluzioni di alcuni esercizi

Algoritmo di Dijkstra per la costruzione dei cammini minimi con sorgente singola

/*
**  dijkstra.c
**
**  Letto in input un grafo orientato e connesso, rappresentato
**  con una matrice di adiacenza e tale che ad ogni spigolo
**  (u,v) sia associato un peso non negativo w(u,v), per ogni
**  vertice v calcola il minimo cammino per raggiungere v
**  partendo dalla sorgente s (letta in input). Il programma
**  e' una codifica in C dell'algoritmo di Dijkstra. La coda H
**  viene rappresentata come una coda di priorita' realizzata
**  con un heap binario.
**
**  Pseudo-codifica dell'algoritmo:
**
**  Dijkstra(G, W, s)
**    per ogni v in V(G) ripeti:
**      d(v) = infinito
**      padre(v) = nil
**    end
**    d(s) = 0
**    aggiungi ogni vertice v alla coda di priorita' H
**    fintanto che H non e` vuoto ripeti:
**      sia u il l'elemento di H con d(u) minima
**      estrai u da H
**      per ogni vertice v adiacente a u ripeti:
**        se d(v) > d(u) + w(u,v) allora
**          d(v) = d(u) + w(u,v)
**          padre(v) = u
**          riposiziona v in H
**        end
**      end
**    end
**  END
**
*/


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

#define MAX 50

/*
 *  Elemento della lista di adiacenza del grafo
 */

struct nodo {
  int info;
  int w;
  struct nodo *next;
};

/*
 *  Scambia il contenuto dei due indirizzi di memoria x e y
 *  ricevuti come argomento.
 */

void scambia(int *x, int *y) {
  int z;
  z = *x;
  *x = *y;
  *y = z;
  return;
}

/*
 *  Legge in input la lista dei vertici adiacenti ad
 *  un vertice del grafo. Oltre a memorizzare il vertice
 *  adiacente in p->info, memorizza il peso dello spigolo 
 *  in p->w.
 */

struct nodo *leggiLista(void) {
  int i, n;
  struct nodo *p, *primo;
  printf("Numero di elementi: ");
  scanf("%d", &n);
  primo = NULL;
  for (i=0; i<n; i++) {
    p = malloc(sizeof(struct nodo));
    printf("Vertice e peso: ");
    scanf("%d %d", &p->info, &p->w);
    p->next = primo;
    primo = p;
  }
  return(primo);
}

/*
 *  Legge in input il grafo e lo rappresenta attraverso
 *  n liste di adiacenza.
 */

int leggiGrafo(struct nodo *G[]) {
  int i, n;
  printf("Numero di vertici: ");
  scanf("%d", &n);
  for (i=0; i<n; i++) {
    printf("Lista di adiacenza del vertice %d.\n", i);
    G[i] = leggiLista();
  }
  return(n);
}

/*
 *  Visualizza in output una lista di adiacenza del grafo
 */

void stampaLista(struct nodo *p) {
  while (p != NULL) {
    printf("%2d (%d) --> ", p->info, p->w);
    p = p->next;
  }
  printf("NULL\n");
  return;
}

/*
 *  Visualizza in output tutte le liste di adiacenza che
 *  compongono il grafo.
 */

void stampaGrafo(struct nodo *G[], int n) {
  int v;
  for (v=0; v<n; v++) {
    printf("%3d: ", v);
    stampaLista(G[v]);
  }
  return;
}

/*
 *  Estrae l'elemento u dalla coda di priorita' H rappresentata
 *  come un heap binario, con l'elemento minimo posto sulla radice
 *  (min-heap)
 */

int heapExtract(int H[], int Hind[], int d[]) {
  int i, min;
  min  = H[1];
  H[1] = H[H[0]];
  Hind[H[1]] = 1;
  H[0] = H[0] -1 ;
  i = 1;
  while (i < H[0]/2 && (d[H[i]] > d[H[2*i]] || d[H[i]] > d[H[2*i+1]])) {
    if (d[H[2*i]] > d[H[2*i+1]]) {
      scambia(&H[i], &H[2*i]);
      Hind[H[i]] = i;
      Hind[H[2*i]] = 2*i;
      i = 2*i;
    } else {
      scambia(&H[i], &H[2*i+1]);
      Hind[H[i]] = i;
      Hind[H[2*i+1]] = 2*i+1;
      i = 2*i+1;
    }
  }
  if (i == H[0]/2 && d[H[i]] > d[H[2*i]]) {
    scambia(&H[i], &H[2*i]);
    Hind[H[i]] = i;
    Hind[H[2*i]] = 2*i;
  }
  return(min);
}

/*
 *  Ricolloca il vertice v nell'Heap dopo che ne è stato diminuito
 *  il valore d[v].
 */

void heapRelocate(int H[], int Hind[], int v, int d[]) {
  int i;
  i = Hind[v];
  while (i > 1 && d[H[i]] < d[H[i/2]]) {
    scambia(&H[i], &H[i/2]);
    Hind[H[i]] = i;
    Hind[H[i/2]] = i/2;
    i = i/2;
  }
  return;
}

/*
 *  Inizializza l'heap H inserendo s sulla radice e gli altri
 *  vertici a seguire. 
 *  Hind[v] e' l'indice di v nell'array H
 */

void heapInit(int H[], int Hind[], int n, int s) {
  int v, k=2;
  H[0] = n;
  H[1] = s;
  Hind[s] = 1;
  for (v=0; v<n; v++) {
    if (v != s) {
      H[k] = v;
      Hind[v] = k;
      k++;
    }
  }
  return;
}
      
/*
 *  Algoritmo di Dijkstra per il calcolo del cammino
 *  di costo minimo dalla sorgente s
 */

void dijkstra(struct nodo *G[], int n, int d[], int pi[], int s) {
  int u, v, H[MAX], Hind[MAX], infinito = INT_MAX;
  struct nodo *p;
  for (v=0; v<n; v++) {
    d[v] = infinito;
    pi[v] = -1;
  }
  d[s] = 0;
  heapInit(H, Hind, n, s);
  while (H[0] != 0) {
    u = heapExtract(H, Hind, d);
    p = G[u];
    while (p != NULL) {
      v = p->info;
      if (d[v] > d[u] + p->w) {
        pi[v] = u;
        d[v] = d[u] + p->w;
        heapRelocate(H, Hind, v, d);
      }
      p = p->next;
    }
  }
  return;
}

/*
 *  Funzione principale che implementa l'algoritmo di Dijkstra.
 */

int main(void) {
  int d[MAX], pi[MAX], n, s, v;
  struct nodo *G[MAX];
  n = leggiGrafo(G);
  stampaGrafo(G, n);
  printf("Sorgente: ");
  scanf("%d", &s);
  dijkstra(G, n, d, pi, s);
  for (v=0; v < n; v++) {
    printf("d[%d] = %3d, pi[%d] = %3d\n", v, d[v], v, pi[v]);
  }
  return(0);
}