Ricerca Operativa II
prova scritta del 22 gennaio 2000
Riciclaggio
Il grafo di figura rappresenta una rete di distribuzione single-commodity. Ogni arco corrisponde a una tratta della rete ed è associato a due pesi: il primo rappresenta la capacità della tratta, il secondo il costo sostenuto per inviare un flusso unitario attraverso la tratta. Si vuole sviluppare un algoritmo per calcolare una distribuzione di flusso a costo minimo.
A questo scopo si desidera riutilizzare un codice che realizza il ben noto algoritmo di Dijkstra per il calcolo di un (s, t)-cammino di lunghezza minima su un grafo. Come si può procedere? L'algoritmo sviluppato è in grado di determinare una distribuzione di flusso ottima nel caso in esame?