[C] Algoritmo sui grafi

[Brteo]

Salve a tutti, ho un problema con un algoritmo che devo implementare come elaborato per la mia università, non so se qualcuno saprà darmi un'idea almenochè non ha già incontrato problemi simili, comunque ci provo.

input:
* un grafo G,
* un albero di copertura minimo per G
* due archi i e j,

testo:
Calcola l'albero di copertura minimo per il grafo G' ottenuto da G scambiando i pesi degli archi i,j. L'abero di copertura minimo in input vi deve essere di aiuto per velocizzare il calcolo della copertura minima di G'. Potete assumere che il grafo G abbia tutti pesi distinti (nota: per grafi i cui pesi sono tutti distinti l'abero di copertura minimo e' unico).

[variabilepippo]

Salve a tutti, ho un problema con un algoritmo che devo implementare come elaborato per la mia università, non so se qualcuno saprà darmi un'idea almenochè non ha già incontrato problemi simili, comunque ci provo.

Hai dimenticato di indicare quali difficoltà incontri nell'implementazione dell'algoritmo.

[Brteo]

Più che altro non ho idee sull'implementazione tranne che pensavo di evitare il calcolo del MST se gli archi cambiati sono superiori come peso a quelli già presenti nel MST di ingresso, in quel caso l'MST rimarrebbe lo stesso senza la necessità di ricalcolarlo. Altrimenti non so come velocizzare il calcolo.