# Finding the shortest route using Dijkstra's algorithm

Blog Post created by xander_bakker on Dec 23, 2014

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
route = result
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], dct_nodes[node_id])

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: [r, (r.firstPoint.X, r.firstPoint.Y),
(r.lastPoint.X, r.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
if not start in dct_nodes.values():
cnt += 1
node_id = node_format.format(cnt)
dct_nodes[node_id] = start

end = line
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, dct_nodes)
end = getNodeID(line, dct_nodes)
dct_lines_nodes[oid] = [line, 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():
nodes_start = [[line, line] for line in dct_lines_nodes.values() if line == node_id]
for node in nodes_start:
nodes_end = [[line, line] for line in dct_lines_nodes.values() if line == node_id]
for node in nodes_end:
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.firstPoint
node_start = (pnt.X, pnt.Y)
node_start = getNodeID(node_start, dct_nodes)
elif cnt == 2:
pnt = row.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!