These are the packages I'm importing. I probably won't end-up using half of them.
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.
#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.
#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.
#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."
#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)]))