Lad P være en korteste vej fra en knude s til en knude t i en graf G med ikke-negative kantvægte. Vi betragter følgende problem: for hver kant e på P, bestem længden af en korteste vej i G fra s til t, der undgår e. Dette er kendt som replacement paths-problemet. Vi giver en algoritme med O(nlog n) køretid og O(n) pladsforbrug for planare orienterede grafer, hvor n er antallet af knuder. Dette er en forbedring af en tidligere O(n(log n)^2)-tids-algoritme.