Givet en planar orienteret graf med n knuder, med reelle kantvægte og med ingen kredse af negativ vægt, viser vi, hvordan afstanden fra en given knude til alle andre knuder i grafen kan bestemmes i O(n(log n)^2/loglog n) tid med O(n) plads. Dette er en forbedring af en O(n(log n)^2)-tids-algoritme af Klein et al.