Many biological systems require extensive networks to transport resources and information. Biological networks must trade-off network efficiency with the risk of network failure. Yet, biological networks develop in the absence of centralised control from the interactions of many components. Moreover, many biological systems need to be able to adapt when conditions change and the network requires modification. We used the slime mould Physarum polycephalum (Schwein) to study how the organism adapts its network after disruption. To allow us to determine the efficiency of the constructed networks, we used a well-known shortestpath problem: the Towers of Hanoi maze. We first show that while P. polycephalum is capable of building networks with minimal length paths through the maze, most solutions are sub-optimal. We then disrupted the network by severing the main connecting path while opening a new path in the maze. In response to dynamic changes to the environment, P. polycephalum reconstructed more efficient solutions, with all replicates building networks with minimal length paths through the maze after network disruption. While P. polycephalum altered some of its existing network to accommodate changes in the environment, it also reconstructed large sections of the network from scratch. We compared the results obtained from P. polycephalum with those obtained using another distributed biological system: ant colonies. We hypothesise that network construction in ants hinges upon stronger positive feedback than for slime mould, ensuring that ants converge more accurately upon the shortest path but are more constrained by the history of their networks in dynamic environments.