How about removing the lines that cross a circle of the shortest path and recalculating nodes which lost a connection?