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
**
**  Marco Liverani (liverani@mat.uniroma3.it) - Dicembre 2023
*/


#include 
#include 
#include 

#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; iinfo, &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 ", 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 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; vinfo;
      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);
}