GIS Shortest Path

How the GIS Shortest Path works, and what it assumes

The network you load is turned into a graph: every line becomes an edge, and every place two lines share an endpoint becomes a node. That second step is the one that decides whether routing works at all, because two lines meeting at a junction almost never carry identical coordinates — they were digitised separately, or exported with different rounding. Endpoints within the junction tolerance are treated as the same node, which is why that setting is exposed rather than hidden.

A crossing is not a junction. Two lines that cross on screen without sharing an endpoint stay unconnected, because a duct passing under a road is not a place you can turn. Welding every visual crossing would invent routes that do not exist on the ground, so the tool does not do it.

Your two points are almost never on a node, so each is projected onto the nearest edge and that edge is split at the projection for the duration of the search. Distances are measured with the haversine formula on the WGS 84 mean radius: longitude and latitude are angles, and one degree of longitude is about 111 km at the equator and nothing at the poles, so degrees are never treated as metres.

Dijkstra settles the nearest unvisited node repeatedly until it reaches the destination, using a binary heap so a large network does not degrade into a repeated scan. A* adds a straight-line estimate of the distance still to go, which never overestimates and so cannot change the answer — but only while cost is distance. Choose lowest cost or fastest route and that estimate stops being a valid lower bound, so the tool quietly uses Dijkstra and tells you it did, rather than returning a route it cannot stand behind.

Using the GIS Shortest Path

• Measuring the cable run between two points on a fibre network without opening a desktop GIS.
• Checking whether a duct network is actually connected end to end, or whether two halves only appear to meet.
• Finding which segments a route uses, so the ones that matter can be prioritised for survey or repair.
• Comparing the shortest physical path against a weighted one when some segments cost more to traverse.
• Testing that an exported network routes correctly before loading it into a larger system.

A worked example

A small network with a direct link and a longer detour:

{
  "type": "FeatureCollection",
  "features": [
    { "type": "Feature", "properties": { "id": "direct", "status": "inactive" },
      "geometry": { "type": "LineString",
        "coordinates": [[77.100, 28.600], [77.120, 28.600]] } },
    { "type": "Feature", "properties": { "id": "north-a" },
      "geometry": { "type": "LineString",
        "coordinates": [[77.100, 28.600], [77.110, 28.620]] } },
    { "type": "Feature", "properties": { "id": "north-b" },
      "geometry": { "type": "LineString",
        "coordinates": [[77.110, 28.620], [77.120, 28.600]] } }
  ]
}

Routing from 77.100, 28.600 to 77.120, 28.600 does not take the direct link, because its status is inactive and excluded statuses are left out of the graph entirely. The answer comes back along the detour:

Distance:  4.857 km
Segments:  2
Algorithm: Dijkstra
Route:     north-a, north-b

Change the status to active and the same request returns 1.953 km in one segment. If instead the two halves of the network share no endpoint at all, the answer is No route found between the selected points. — never a straight line drawn between them.

Where this comes up in GIS work

1. Choose a GeoJSON file of LineStrings, or select Load example network to try it.
2. Click the plot once to set the source and again to set the destination, or type coordinates as longitude, latitude.
3. Pick the algorithm and what to optimise for: shortest distance, lowest cost or fastest route.
4. Adjust the junction tolerance if segments that should meet are not connecting.
5. Select Calculate route, then Export route GeoJSON to download the result.

When the output looks wrong

No route found between the selected points

The two points are on parts of the network that are not connected. Most often the segments meet visually but do not share an endpoint, so raise the junction tolerance. Failing that, a one-way segment may be blocking the only path: tick Ignore one-way to test whether direction is the cause.

The source or destination is too far from the network

Clicks more than a kilometre from any segment are refused rather than snapped across open ground, because a route that starts a kilometre from where you clicked is not the route you asked for. Zoom in on the plot and click nearer a line.

The plot is a solid block rather than separate lines

A network with thousands of segments has more lines than the plot has pixels across, so at page width they merge into one mass. Drag the bottom edge of the plot to make it taller, or select Full screen to give it the whole page. Networks beyond 8,000 segments also draw only the first 8,000; the readout says so, and routing still uses every one of them.

Segments that cross on the plot are not connected

A crossing is not a junction. Two lines that cross without sharing an endpoint stay separate, because a duct passing under a road is not a place you can turn. If they genuinely meet, the network needs a shared endpoint there, or split the lines at the crossing before exporting.

A* was requested but the result says Dijkstra

A* relies on straight-line distance never exceeding the real distance. That holds when cost is distance, and stops holding as soon as a weight is applied, so under lowest cost or fastest route the tool uses Dijkstra to keep the answer optimal rather than returning a plausible but wrong one.

That network is no longer loaded

Loaded networks are held for twenty minutes and then forgotten. Load the file again to carry on; nothing was saved, which is the intended behaviour rather than a fault.

Questions about the GIS Shortest Path