Esercizi e sorgenti dei programmi
Algoritmo di Bellman-Ford per grafi orientati aciclici
L'algoritmo di Bellman-Ford risolve il problema del cammino minimo da una sorgente singola su un grafo con pesi assegnati agli spigoli. La versione dell'algoritmo presentata in questa pagina può operare su grafi orientati aciclici, dal momento che, per ottimizzare l'efficienza dell'algoritmo, viene prodotto un ordinamento topologico dei vertici del grafo mediante la funzione sortTopologico.
La pseudo-codifica dell'algoritmo di Bellman-Ford può essere definita con i seguenti passi:
BELLMANFORD(G, s)
- Input: Un grafo pesato G orientato e aciclico e un vertice s ∈ V(G) scelto arbitrariamente come sorgente della visita
- Output: Un albero di cammini minimi con radice in s costituito dai cammini di costo minimo che da s consentono di raggiungere ogni altro vertice v ∈ V(G)
- per ogni vertice v ∈ V(G) ripeti:
- D(s,v) := ∞, π(v) := NULL
- fine-ciclo
- D(s,s) := 0
- esegui l'ordinamento topologico di V(G)
- per ogni vertice u ∈ V(G) in ordine topologico, ripeti:
- per ogni vertice v ∈ N(u) ripeti:
- se D(s,v) ≥ D(s,u) + W(u,v)
- allora D(s,v) := D(s,u) + W(u,v), π(v) := u
- fine-ciclo
- fine-ciclo
La compilazione del programma richiede l'uso della libreria grafi.c.
/*
** bellmanFord.c
**
** Implementazione dell'algoritmo di Bellman-Ford per il calcolo
** del cammino di costo minimo da una sorgente s su un grafo G
** orientato e aciclico con pesi assegnati ai vertici.
**
** BELLMAN-FORD(G, W, S)
**
** INPUT: Un grafo pesato G orientato e aciclico e un vertice s
** scelto arbitrariamente come sorgente della visita
**
** OUTPUT: Un albero di cammini minimi con radice in s costituito
** dai cammini di costo minimo che da s consentono di raggiungere
** ogni altro vertice v in G
**
** per ogni vertice v di G ripeti:
** D(s,v) := infinito, Pi(v) := NULL
** fine-ciclo
** D(s,s) := 0
** esegui l'ordinamento topologico di V(G)
** per ogni vertice u di G in ordine topologico, ripeti:
** per ogni vertice v adiacente ad u ripeti:
** se D(s,v) >= D(s,u) + W(u,v)
** allora D(s,v) := D(s,u) + W(u,v), Pi(v) := u
** 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 Bellman-Ford
*/
void bellmanFord(grafoPesato *pG, int Pi[]) {
int i, s;
int **D;
elementoLista *p, *q;
grafo G1;
D = malloc(sizeof(int *) * (pG->n + 1));
for (i=1; i<=pG->n; i++)
D[i] = malloc(sizeof(int) * (pG->n + 1));
printf("Sorgente della visita (1-%d): ", pG->n);
scanf("%d", &s);
for (i=1; i <= pG->n; i++) {
D[s][i] = INFINITO;
Pi[i] = -1;
}
D[s][s] = 0;
linkGrafoToGrafoPesato(&G1, pG);
p = sortTopologico(G1);
while (p != NULL) {
q = pG->V[p->info];
while (q != NULL) {
if (D[s][q->info] >= D[s][p->info] + pG->W[p->info][q->info]) {
D[s][q->info] = D[s][p->info] + pG->W[p->info][q->info];
Pi[q->info] = p->info;
}
q = q->next;
}
p = p->next;
}
return;
}
/*
* Funzione principale
*/
int main(void) {
grafoPesato G;
int *Pi, i;
leggiGrafoPesato(&G);
Pi = malloc(sizeof(int)*(G.n+1));
bellmanFord(&G, Pi);
for (i=1; i<=G.n; i++)
printf("%d padre di %d\n", Pi[i], i);
return(0);
}