Situazione complessa su un grafo

[Demin Black Off]

Allora ho il seguente problema:

Ho un grafo orientato che rappresentano delle città, ciascun arco contiene un peso che è la distanza in km. Devo implementare un codice che permetta di determinare attraverso una DIJKSTRA l'albero di copertura minimo che consenta una connessione adsl a tutte le città a partire da una data città "CENTRALE TELECOM", che è UNICA nel grafo.

Ora sorge il vero problema....

Dopo determinaro l'albero di copertura minimo e stampato a video la lunghezza del cavo, bisogna gestire queste situazioni:

Cancellazione di una città
Cancellazione di un arco
Inserimento di un arco
Inserimento di una città

ovviamente facendo in modo che alla fine i percorsi sono sempre di peso minimo.
Non è consetito usare più volte la DIJKSTRA ( altrimenti il problema non sorgeva se potevo usarla in ogni situazione ).

Non so neanche da dove iniziare, per esempio se devo eliminare una città, le città che vengono ad essere "non coperte più" come le ricollego ? Ho notato che esistono una marea di casi particolari

Dati almeno uno spunto anche nella letteratura qualcosa da leggere che lo spieghi