Progetto 4 - Ricerca cammino minimo
Si supponga di avere memorizzato in un file MAPPA
la descrizione di una mappa stradale o ferroviaria indicante
per ogni coppia di città la relativa distanza (in Km) ed eventuali
altre caratteristiche del collegamento tra le due città (ad esempio,
tipo di strada). Si assume che non ci siano limiti a priori alla
complessità (numero di città, numero di collegamenti tra
due città, ecc.) della mappa memorizzata sul file MAPPA.
Realizzare un programma che avvalendosi dei dati memorizzati nel
file MAPPA sia in grado di fornire (almeno) le seguenti funzioni:
Ricerca del cammino minimo tra due città date (città di
partenza e città d'arrivo) con gli eventuali ulteriori vincoli di:
- una o più città intermedie attraverso cui passare
- tipo di collegamento (p.e., autostrade o strade statali nel caso di
mappa stradale, treni rapidi o locali nel caso di mappa
ferroviaria)
- altro
Il programma dovrà mostrare il cammino minimo trovato indicando non
soltanto la distanza totale ma anche tutte le città attraversate.
Dovrà inoltre dare opportuna indicazione nel caso una delle città
fornite non sia presente nell'elenco delle città fornito.
Aggiornamento del file MAPPA con la possibilità di
- immettere nuove città e nuovi collegamenti tra città
esistenti
- cancellare o modificare dati relativi a città e/o
collegamnti esistenti
- visualizzare l'elenco delle città presenti
Tutte le modifiche effettuate devono essere riportate in modo
opportuno anche sul file MAPPA.
SUGGERIMENTI E VINCOLI:
- I dati sul file MAPPA possono essere rapprresentati da
quadruple del tipo:
- Per la realizzazione in C++ si richiede che i dati letti dal
file MAPPA vengano memorizzati in memoria principale come una
struttura dati (astratta) di tipo grafo non orientato.
Per la realizzazione concreta di tale struttura , date le caratteristiche
di dinamicità e di mancanza di limiti sulla dimensione dei dati di
input, si richiede di utilizzare strutture dati dinamiche del tipo
liste concatenate multiple.
Si richiede inoltre di utilizzare per quanto possibile i meccanismi
di ereditarietà e le classi standard offerte dal C++ per
l'implementazione del grafo e delle relative operazioni per la sua
gestione.
- L'immissione dei dati da parte dell'utente deve essere il più
possibile facilitata con l'utilizzo di opportuni menù di comandi.