Finding the shortest route using Dijkstra's algorithm
Last month a user mentioned the Dijkstra algorithm to determine the shortest path between two nodes in a network. My first reaction was to use Network Analyst instead, but to honor the essence of a previous useless post: Japanese visual multiplication with lines using arcpy and a dash of patriotism (Dijkstra was Dutch) made me look into this a little more.
I came across this post; Dijkstra's algorithm for shortest paths « Python recipes « ActiveState Code and from this post I actually used the code from this one; Rebrained! » Blog Archive » Shortest Path – Python . Remember, basic skills for developing code are search, copy and paste…
It is basically recursive code that will ultimately get you the route between two nodes on the network. What you need is a "graph". This is a nested dictionary that lists all the connections between the from and to nodes and the corresponding distances. To be able to use the code I need to convert my "network" into this graph format.
What you need is a network (a simple line featureclass), in which all intersections of lines consist of nodes. You will also need a point feature class containing the start and end point. These points should correspond with nodes of the network.This is the result:
I came up with the following code:
#-------------------------------------------------------------------------------
# Name: dijkstra.py
# Purpose: determine route
#
# Author: xbakker
#
# Created: 02/12/2014
#-------------------------------------------------------------------------------
import arcpy
import sys
def main():
# input featureclasses
fc_red = r"D:\Xander\GeoNet\Dijkstra\fgdb\test.gdb\red"
fc_stops = r"D:\Xander\GeoNet\Dijkstra\fgdb\test.gdb\stops2"
# create line dictionary
dct_lines = createLineDict(fc_red)
# create node and inverted node dictionary
dct_nodes = createNodes(dct_lines)
# update line dictionary with nodes
dct_lines_nodes = combineLinesAndNodes(dct_lines, dct_nodes)
# create graph
dct_graph = createGraph(dct_nodes, dct_lines_nodes)
# determine the node of start and end of route
node_start, node_end = getStartEndNodes(fc_stops, dct_nodes)
# determine route
result = shortestpath(dct_graph, node_start, node_end)
# create line with the result
dist = result[0]
route = result[1]
print "Resulting route : {0}".format(route)
print "Length of the route: {0}\n".format(dist)
cnt = 0
for node_id in route:
cnt += 1
print "{0}\t{1}\t{2}".format(cnt, dct_nodes[node_id][0], dct_nodes[node_id][1])
def createLineDict(fc):
"""Crear dict de lineas con datos relevantes"""
#OBJECTID (line): length, (Xstart, Ystart), (Xend, Yend)
dct_lines = {}
flds = ("OID@", "SHAPE@", "SHAPE@LENGTH")
dct_lines = {r[0]: [r[2], (r[1].firstPoint.X, r[1].firstPoint.Y),
(r[1].lastPoint.X, r[1].lastPoint.Y)]
for r in arcpy.da.SearchCursor(fc, flds)}
return dct_lines
def createNodes(dct):
"""Crear dict de nodos"""
node_format = "node_{0}"
cnt = 0
dct_nodes = {}
dct_nodes_inv = {}
for line in dct.values():
start = line[1]
if not start in dct_nodes.values():
cnt += 1
node_id = node_format.format(cnt)
dct_nodes[node_id] = start
end = line[2]
if not end in dct_nodes.values():
cnt += 1
node_id = node_format.format(cnt)
dct_nodes[node_id] = end
return dct_nodes
def combineLinesAndNodes(dct_lines, dct_nodes):
"""Crear dict con lineas y codigo de nodos"""
dct_lines_nodes = {}
for oid, line in dct_lines.items():
start = getNodeID(line[1], dct_nodes)
end = getNodeID(line[2], dct_nodes)
dct_lines_nodes[oid] = [line[0], start, end]
return dct_lines_nodes
def getNodeID(pnt, dct_nodes):
for node_id, coords in dct_nodes.items():
if coords == pnt:
return node_id
break
def createGraph(dct_nodes, dct_lines_nodes):
res = {}
for node_id in dct_nodes.keys():
links = {}
nodes_start = [[line[2], line[0]] for line in dct_lines_nodes.values() if line[1] == node_id]
for node in nodes_start:
links[node[0]] = node[1]
nodes_end = [[line[1], line[0]] for line in dct_lines_nodes.values() if line[2] == node_id]
for node in nodes_end:
links[node[0]] = node[1]
res[node_id] = links
return res
def getStartEndNodes(fc, dct_nodes):
cnt = 0
with arcpy.da.SearchCursor(fc, ("SHAPE@")) as curs:
for row in curs:
cnt += 1
if cnt == 1:
pnt = row[0].firstPoint
node_start = (pnt.X, pnt.Y)
node_start = getNodeID(node_start, dct_nodes)
elif cnt == 2:
pnt = row[0].lastPoint
node_end = (pnt.X, pnt.Y)
node_end = getNodeID(node_end, dct_nodes)
else:
break
return node_start, node_end
def shortestpath(graph,start,end,visited=[],distances={},predecessors={}):
"""Find the shortest path between start and end nodes in a graph"""
# we've found our end node, now find the path to it, and return
if start==end:
path=[]
while end != None:
path.append(end)
end=predecessors.get(end,None)
return distances[start], path[::-1]
# detect if it's the first time through, set current distance to zero
if not visited:
distances[start]=0
# process neighbors as per algorithm, keep track of predecessors
for neighbor in graph[start]:
if neighbor not in visited:
neighbordist = distances.get(neighbor,sys.maxint)
tentativedist = distances[start] + graph[start][neighbor]
if tentativedist < neighbordist:
distances[neighbor] = tentativedist
predecessors[neighbor]=start
# neighbors processed, now mark the current node as visited
visited.append(start)
# finds the closest unvisited node to the start
unvisiteds = dict((k, distances.get(k,sys.maxint)) for k in graph if k not in visited)
closestnode = min(unvisiteds, key=unvisiteds.get)
# now we can take the closest node and recurse, making it current
return shortestpath(graph,closestnode,end,visited,distances,predecessors)
if __name__ == '__main__':
main()Have fun!