These are the packages I'm importing. I probably won't end-up using half of them.

In [ ]:
import matplotlib
import matplotlib.pyplot as plt
from random import randint
import random
import copy
import numpy as np
import operator
from matplotlib import rcParams
rcParams['mathtext.default'] = 'regular'
%matplotlib inline
plt.rc('text', usetex=True)
plt.rc('font', family='serif')


Given a node, we need a function that tells us what the unvisited nearest-neighbors are to that node.

To do this, we enumerate all the possible neighbors of the given node, and compare them to a list of all the nodes that exist in the graph. The possible neighbors of the node that also actually exist are output from the function.

In [ ]:
#node: The node for which we would like the near-neighbors on the graph. A length-D list in D dimensions.
#node_list: list all nodes in the graph that are still unvisited
#nlist: list of the nearest-neighbors for chosen node on the graph
def neighbor_list(node,node_list):

#Dimensionality of the graph
dim=len(node)

#Initialize the list of nearest neighbors of node
nlist=[]

#Determine the nearest neighbors, checking to make sure you don't "fall-off the graph"
for D in range(dim):
up_shift=copy.copy(node)
up_shift[D]=node[D]+1
down_shift=copy.copy(node)
down_shift[D]=node[D]-1
if up_shift in node_list:
nlist.append(up_shift)
if down_shift in node_list:
nlist.append(down_shift)

return nlist


Given a list of nodes, this little function will just plot the nodes.

In [ ]:
#node_list: List of the nodes we want to plot
#banned_nodes: The nodes we are not allowed to pass through when traversing the graph
#target_node: The target node
def plot_nodes(node_list,banned_nodes,target_node):

xb=[]
yb=[]
for node in banned_nodes:
xb.append(node[0])
yb.append(node[1])

x=[]
y=[]
for node in node_list:
x.append(node[0])
y.append(node[1])

#Plot the banned nodes in blue
plt.plot(xb,yb,marker='o',markersize=15,linewidth=0,color='b')

#Color the target node green
plt.plot([target_node[0]],target_node[1],marker='o',markersize=10,linewidth=0,color='g')

#Plot the path through the graph in black
plt.plot(x,y,marker='o',markersize=10,linewidth=0,color='k')

#Color the initial node red
plt.plot([x[0]],y[0],marker='o',markersize=10,linewidth=0,color='r')


We're going to implement Dijikstra's algorithm in Euclidean-2D. This is a famous algorithm for determining the shortest path between two nodes in a graph.

In [ ]:
#Implement Dijikstra's algorithm for a 2D graph

#Size of the grid
L=5

#Create a dictionary keeping track of the tentative distance between the initial and target nodes
#at each step.
dist={}

#Create a list keeping track of which nodes we have visited.
visited=[]

#Create a list keeping track of which nodes we have not yet visited.
unvisited=[]

#Ignore this for now
banned_nodes=[]

#We now initialize the "distance dictionary" with some initial values
for x in range(L):
for y in range(L):

#Create a list of unvisited nodes
#Initially, this list includes every node
unvisited.append([x,y])

#Set the distance for every node to "infinity" at the beginning.
dist[(x,y)]=10^10*L

#Remove the nonexistant nodes from the unvisited list, so we know to never go there
unvisited=[x for x in unvisited if x not in banned_nodes]

#Pick the initial node.
#This the node we want to start from.
inode=random.choice(unvisited)
print('The initial node coordinate is: '+np.str(inode))

#Pick the target node.
#We want to find the minimal distance between the initial and target nodes
tnode=random.choice(unvisited)
print('The target node coordinate is: '+np.str(tnode))

#The initial node is a distance of 0 from itself of course.
dist[tuple(inode)]=0

#We now set the current node to be the initial node
cnode=copy.copy(inode)

print('')

#A counter to keep track of how many iterations we've gone through
c=0

#Keep iterating to new nodes until we reach the target node
while tnode in unvisited:

print('The current node is: '+np.str(cnode))

#These are the unvisited nearest-neighbors of the current node that we will check
neighbors=neighbor_list(cnode,unvisited)
print("The current neighbors are: "+np.str(neighbors))

#Compute a tentative distance between the neighbors of the current node and the initial node
#We only update the dist dictionary if tent_dist[(x,y)]<dist[(x,y)]
tent_dist={}

#Compute distances from the initial node to its neighboring nodes
for n in neighbors:
tent_dist[tuple(n)]=dist[tuple(cnode)]+1

#If the new tentative distance is less than then currently recorded distance for that node then update.
if tent_dist[tuple(n)]<dist[tuple(n)]:
dist[tuple(n)]=tent_dist[tuple(n)]

#We have now checked all the neighbors of the current node, so we remove it from the unvisited list,
#and add it to the visited list
unvisited.remove(cnode)
visited.append(cnode)

#The new current node (cnode) is whichever unvisited node has the shortest recorded distance thus far
unvisited_dist = { tuple(unvisited_node): dist[tuple(unvisited_node)] for unvisited_node in unvisited }
cnode=list(min(unvisited_dist.iteritems(), key=operator.itemgetter(1))[0])

c+=1
print('Iteration: '+np.str(c))
print('So far we have visited '+np.str(len(visited))+' nodes!')

#Let's plot the nodes we've visited so far
plt.figure(c)
plt.title('Dijkstra Algorithm Iteration '+np.str(c))
if tnode not in unvisited:
plt.title('The minimum path length is '+np.str(dist[tuple(tnode)])+'!')
plt.xlim([-1,L])
plt.ylim([-1,L])
plot_nodes(visited,banned_nodes,tnode)
if c<10:
plt.savefig('dijkstra_2d_iteration_0'+np.str(c)+'.png',dpi=200,bbox_inches='tight')
else:
plt.savefig('dijkstra_2d_iteration_'+np.str(c)+'.png',dpi=200,bbox_inches='tight')

print('#########################################################')
print('')

print('The Dijkstra minimum path length is '+np.str(dist[tuple(tnode)]))


This implementation is going to be the same as before, but now we will specify a list of nodes that don't "exist" in the graph, so our algorithm will have to go "around them."

In [ ]:
#Implement Dijikstra's algorithm for a 2D graph

#Size of the grid
L=5

#Create a dictionary keeping track of the tentative distance between the initial and target nodes
#at each step.
dist={}

#Create a list keeping track of which nodes we have visited.
visited=[]

#Create a list keeping track of which nodes we have not yet visited.
unvisited=[]

#Now we will specify the nodes that we don't want our path to pass through!
banned_nodes=[[2,1],[2,2],[2,3],[1,2],[3,2]]

#We now initialize the "distance dictionary" with some initial values
for x in range(L):
for y in range(L):

#Create a list of unvisited nodes
#Initially, this list includes every node
unvisited.append([x,y])

#Set the distance for every node to "infinity" at the beginning.
dist[(x,y)]=10^10*L

#Remove the nonexistant nodes from the unvisited list, so we know to never go there
unvisited=[x for x in unvisited if x not in banned_nodes]

#Pick the initial node.
#This the node we want to start from.
inode=random.choice(unvisited)
print('The initial node coordinate is: '+np.str(inode))

#Pick the target node.
#We want to find the minimal distance between the initial and target nodes
tnode=random.choice(unvisited)
print('The target node coordinate is: '+np.str(tnode))

#The initial node is a distance of 0 from itself of course.
dist[tuple(inode)]=0

#We now set the current node to be the initial node
cnode=copy.copy(inode)

print('')

#A counter to keep track of how many iterations we've gone through
c=0

#Keep iterating to new nodes until we reach the target node
while tnode in unvisited:

print('The current node is: '+np.str(cnode))

#These are the unvisited nearest-neighbors of the current node that we will check
neighbors=neighbor_list(cnode,unvisited)
print("The current neighbors are: "+np.str(neighbors))

#Compute a tentative distance between the neighbors of the current node and the initial node
#We only update the dist dictionary if tent_dist[(x,y)]<dist[(x,y)]
tent_dist={}

#Compute distances from the initial node to its neighboring nodes
for n in neighbors:
tent_dist[tuple(n)]=dist[tuple(cnode)]+1

#If the new tentative distance is less than then currently recorded distance for that node then update.
if tent_dist[tuple(n)]<dist[tuple(n)]:
dist[tuple(n)]=tent_dist[tuple(n)]

#We have now checked all the neighbors of the current node, so we remove it from the unvisited list,
#and add it to the visited list
unvisited.remove(cnode)
visited.append(cnode)

#The new current node (cnode) is whichever unvisited node has the shortest recorded distance thus far
unvisited_dist = { tuple(unvisited_node): dist[tuple(unvisited_node)] for unvisited_node in unvisited }
cnode=list(min(unvisited_dist.iteritems(), key=operator.itemgetter(1))[0])

c+=1
print('Iteration: '+np.str(c))
print('So far we have visited '+np.str(len(visited))+' nodes!')

#Let's plot the nodes we've visited so far
plt.figure(c)
plt.title('Dijkstra Algorithm Iteration '+np.str(c))
if tnode not in unvisited:
plt.title('The minimum path length is '+np.str(dist[tuple(tnode)])+'!')
plt.xlim([-1,L])
plt.ylim([-1,L])
plot_nodes(visited,banned_nodes,tnode)
if c<10:
plt.savefig('dijkstra_2d_iteration_0'+np.str(c)+'.png',dpi=200,bbox_inches='tight')
else:
plt.savefig('dijkstra_2d_iteration_'+np.str(c)+'.png',dpi=200,bbox_inches='tight')

print('#########################################################')
print('')

print('The Dijkstra minimum path length is '+np.str(dist[tuple(tnode)]))