Radiation doses received by workers during their movement within areas contaminated as a result of events and activities, leading to emergency or existing exposure situations, may provide a substantial contribution to total external exposure during remediation work. This paper describes an approach to minimise worker external exposure in these circumstances, based on graph theory. The paper describes several tasks, including: searching for a route with the lowest dose, searching for an optimal bypass with a given set of control points and searching for the optimal road network coverage. Classical graph theory algorithms have been used (Dijkstra's algorithm, Chinese postman problem and travelling salesman problem). Algorithms for solving the above mentioned problems have been developed and were included in the information-analytical system for radiation safety. This software has been applied for optimisation of protection during remediation work at the Andreeva Bay site of temporary storage for spent fuel and radioactive waste in the Kola Peninsula, both in the context of existing exposure situations and improving the preparedness for emergency exposure situations.