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);
}