Un immenso grafo G è memorizzato in una banca dati remota. E’ possibile accederne ai parametri utilizzando le funzioni:

• nodi(): integer {fornisce il numero dei nodi di G}
• archi(): integer {fornisce il numero di archi di G}
• arco(u,v): boolean {se restituisce "true", allora uv Î E(G), altrimenti uv Ï E(G)}
• costo(u,v): real {se uv Î E(G) fornisce il costo di percorrenza di uv, altrimenti dà errore}

Si desidera determinare il cammino di lunghezza minima tra il nodo 1 e il nodo n = nodi() utilizzando il simplesso su reti. L’elaboratore locale di cui disponete presenta tuttavia dei limiti di memoria. Codificate dunque il metodo utilizzando meno memoria possibile.

Ovviamente, la vostra codifica reggerà fino a un certo punto, dopodiché, riducendo ulteriormente la memoria disponibile, non sarà più in grado di funzionare. E’ possibile concepire una routine di compressione del grafo che consenta di superare questo limite almeno in taluni casi? Dopo averla realizzata, sperimentatela sul grafo disegnato qui sotto specificando il limite di memoria entro il quale il vostro algoritmo è in grado di terminare correttamente.