# Incorrect Shortest Paths

I compute shortest paths between ports. However, some of the resulting paths are simply incorrect.

Consider the following example where coast is multi-polygon object of the planet's landmass (e.g. based on GSHHG).

# Load packages
packs <- list("tidyverse", "raster", "sf", "tmaptools", "gdistance", "fasterize")
lapply(packs, require, character.only = T)

# Geocode ports
brisbane <- geocode_OSM("Brisbane, Australia", as.sf = T, geometry = "point")
liverpool <- geocode_OSM("Liverpool", as.sf = T, geometry = "point")

# Derive transition layer
tr_paths <- raster(crs = "+proj=longlat +datum=WGS84 +no_defs", vals = 1, resolution = c(1/8, 1/8), ext = extent(c(-180, 180, -90, 90)))
tr_paths <- fasterize(coast, tr_paths) %>%
mask(tr_paths, ., inverse = T, updatevalue = 1000000) %>%
transition(., function(x) 1/mean(x), directions = 8, symm = T) %>%
geoCorrection(., type = "c", scl = F)

# Derive shortest path
path <- shortestPath(tr_paths, as(brisbane, "Spatial"), as(liverpool, "Spatial"), output= "SpatialLines") %>%
st_as_sf()


This is the resulting path:

The problem appears to mostly affect particularly long paths. Shorter connections, e.g. between Recife in Brazil and Liverpool in the UK, are correctly computed.

The gdistance::shortestPath function that I use employs Dijkstra's algorithm implemented via the igraph package. Any ideas why that function produces such odd results? Does igraph change its optimization above a certain path length?

• I don't use R so don't really understand your code, but from your screenshot it looks like you cross the international date line where you go from +180° to -180°Longitude. This usually screws up most algorithms, may be its to do with that? Commented Dec 6, 2020 at 18:00

This looks like the correct path, but it is badly drawn on this projection.

The route heads north out of Brisbane, then turns right and hits the edge of the map. The red line across the world is actually zero metres long. Then the route continues through the Bering Strait and goes north further than the valid EPSG 3857 projection limit of 85N. That explains the excursion into the white space. It probably gets very close to, if not on, the N pole and then heads south to England.

The route is composed of straight lines and 45 degree lines because the algorithm only considers the 8-way nearest neighbours for any step, so all steps are either N,S,E,W or NW, NE, SE, SW. When routing across a constant cost space the route will be straight lines axis-aligned or at 45 degrees. The algorithm cant spot that it can short-cut across from Brisbane to the Bering Strait because it never looks further than the nearest cell neighbour, and going N until it has to go NE (at 45 degrees) is the same distance as the same number of North-steps and NE-degree steps in any order. Even if it did mix up the N and NE steps to visually approximate a straight line, the total line length would be the same since it would be made up of the same segments.