The question is pretty much in the title.

Is there a way to route through a road line shapefile using python and some library without having to resort to converting the data into PostGIS/pgrouting or going through desktop software API such as ArcGIS and QGIS?


3 Answers 3


The link given by MappaGnosis is the first attempt to implement Graph theory algorithms in Python (by Guido van Rossum, the creator of Python).

Since, many modules were developed:

One of the most comprehensive is NetworkX, mentioned before in GS

import networkx  as nx  
graph = nx.read_shp('lines.shp')  
print graph.nodes()  
[(1.0, 2.0), (3.0, 2.0),...]  
print graph.edges()
[((1.0, 2.0), (1.0, 1.0)),...]

Result with matplotlib
enter image description here

Result with graphviz:
enter image description here

A* Algorithm

def dist(a, b):
   (x1, y1) = a
   (x2, y2) = b
    return ((x1 - x2) ** 2 + (y1 - y2) ** 2) ** 0.5

print(nx.astar_path(graph,(3.0,2.0),(1.0, 1.0),dist))
[(3.0, 2.0), (2.0, 1.0), (1.0, 1.0)]

and you can export the results:

to shapefiles:

nx.write_shp(graph, ‘/shapefiles’)

to ogr geometries:

from osgeo import ogr
line = osgeo.ogr.Geometry(ogr.wkbLineString)
from points in (nx.astar_path(graph,(3.0,2.0),(1.0, 1.0),dist)):

print line.ExportToWkt()
LINESTRING (3 2 0,2 1 0,1 1 0)

or to shapely geometries:

from shapely.geometry import LineString
line = LineString(nx.astar_path(graph,(3.0,2.0),(1.0, 1.0),dist))
print line.wkt
LINESTRING (3.00 2.00, 2.00 1.00, 1.00 1.00)

enter image description here

  • This is a beautiful answer. Thanks a lot for clarifying it so neatly. Now that I look at your example, I have an additional question, is it possible to do routing on any point on the line segment? or is it always from the nodes?
    – dassouki
    Commented Jul 3, 2013 at 17:22

'Yes' is the short answer. However, you will need to implement the A* algorithm. This link may be helpful for your implementation. To read the shapefile you will probably want to use the GDAL/OGR python libraries (and if you are on Windows I strongly recommend the 'gisinternals' link).


Yes! A short answer, but I implement this little functionality in python-s2g (https://github.com/caesar0301/python-s2g).

import s2g
import networkx as nx

sg = s2g.ShapeGraph(shapefile='path/to/roads.shp', resolution=1.0)

assert isinstance(sg.graph, nx.Graph)

Use resolution parameter to adjust the spatial sampling, default 1 km in great circle distance.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.