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)]))