Dijkstra's algorithm in Python plotting path

Question

I need adapted Dijkstra's algorithm below to show coordinates of the shortest path.

I need to also draw the path as well, but I'm having trouble getting the right coordinates to plot.

I use the function mylabel2 assign the coordinates and I will like to plot the path as well. Please see from the comment #mydrawings...

import sys
import matplotlib.pyplot as plt
from pprint import pprint

#Function to label points

def mylabel(x):
    return {
         1:'A',
         2:'B',
         3:'C',
         4:'D',
         5:'E',
         6:'F',
         7:'G',
         8:'H',
    }[x]

#Function to derive coordinates

def mylabel2(x):
    return {
         'A':([0],[5]),
         'B':([1],[0]),
         'C':([5],[1]),
         'D':([2],[4]),
         'E':([3],[6]),
         'F':([0],[7]),
         'G':([4],[8]),
         'H':([6],[2])
    } [x]

#Adjancency and State Matrix    

Adj_Matrix = [[0, 20, 0, 0, 0, 0, 15, 0],
             [20, 0, 8, 9, 0, 0, 0, 0],
             [0,  8,  0,  6, 15, 0, 0, 10], 
             [0, 9, 6, 0, 7, 0, 0, 0],
             [0, 0, 15, 7, 0, 22, 18, 0],
             [0, 0, 0, 0, 22, 0, 0, 0],
             [15, 0, 0, 0, 18, 0, 0, 0],
             [0, 0, 10, 0, 0, 0, 0, 0]]


Coord_Matrix_x=[0, 1, 5, 2, 3, 0, 4, 6]
Coord_Matrix_y=[5, 0, 1, 4, 6, 7, 8, 2]

plt.plot(Coord_Matrix_x, Coord_Matrix_y, 'bo')
plt.axis([-1, 7, -1, 9])    

for i in xrange(8):
        plt.text(Coord_Matrix_x[i]-0.5, Coord_Matrix_y[i], str(mylabel(i+1)))


for i in xrange(8):
    for j in xrange(8):
        if Adj_Matrix[i][j] != 0:
            plt.plot([Coord_Matrix_x[i], Coord_Matrix_x[j]], [Coord_Matrix_y[i], Coord_Matrix_y[j]], 'b')


#Collect Start and End Points
#print 'Give the start point'

#startPoint = int(raw_input()) - 1   
#print 'Give the end point'
#endPoint = int(raw_input()) - 1



#Dijkstra Algorithm 

def dijkstra(graph,start,target):
    inf = 0
    for u in graph:
        for v ,w in graph[u]:
           inf = inf + w
    dist = dict([(u,inf) for u in graph])
    prev = dict([(u,None) for u in graph])
    q = graph.keys()
    dist[start] = 0
    #helper function
    def x(v):
        return dist[v]
    #
    while q != []:
        u = min(q, key=x)
        q.remove(u)
        for v,w in graph[u]:
            alt = dist[u] + w
            if alt < dist[v]:
                dist[v] = alt
                prev[v] = u
    #”way”
    trav = []
    temp = target
    while temp != start:
        trav.append(prev[temp])
        temp = prev[temp]
    trav.reverse()
    trav.append(target)
    return " -> ".join(trav),dist[target]
graph = {
    'A' : [('B',20), ('G', 15)],
    'B' : [('A', 20),('C', 8), ('D', 9)],
    'C' : [('B', 8),('D', 6), ('E', 15), ('H', 10)],
    'D' : [('B', 9),('C', 6),('E', 7)],
    'E' : [('C', 15),('D', 7),('F', 22),('G', 18)],
    'F' : [('E', 22)],
    'G' : [('A', 15),('E', 18)],
    'H' : [('C', 10)]
    }

#pprint(graph)
print
traverse, dist = dijkstra(graph,'F','H')
print traverse




#Drawing of coordinates
mydrawing = traverse.split('-> ')

for i in mydrawing:
    i = i.rstrip()
    print i, '=>', mylabel2(i)
    cc = []
    mycoordinates = mylabel2(i)
    for x in mycoordinates:
        cc.append(x)
        if len(mycoordinates)==2:
            a1 = mycoordinates[0]
            a2 = mycoordinates[1]
            print a1, a2, 'node'
            plt.plot(a1,a2, 'ro')
            #plt.plot(a1,a2, 'b')
            #plt.axis([-1, 7, -1, 9])
    print cc, 'array'



print "Distance:",dist

Maybe you can use networkx.github.io/documentation/networkx-1.9.1/reference/…. When dealing with graph and shortest path, Networkx is a library of choice in the Python world. You can also draw graph : networkx.lanl.gov/reference/drawing.html — Raphaël Braud
– Raphaël Braud, Commented Mar 26, 2015 at 8:43

Nizam Mohamed · Accepted Answer · 2015-03-26 17:03:53Z

4

import sys
import matplotlib.pyplot as plt
from pprint import pprint

#dict to label points
mylabel = {1:'A',2:'B',3:'C',4:'D',5:'E',6:'F',7:'G',8:'H'}

#dict to derive coordinates
mylabel2 = {
         'A':(0,5),
         'B':(1,0),
         'C':(5,1),
         'D':(2,4),
         'E':(3,6),
         'F':(0,7),
         'G':(4,8),
         'H':(6,2)
           }
#Adjancency and State Matrix
Adj_Matrix = [[0, 20, 0, 0, 0, 0, 15, 0],
             [20, 0, 8, 9, 0, 0, 0, 0],
             [0,  8,  0,  6, 15, 0, 0, 10],
             [0, 9, 6, 0, 7, 0, 0, 0],
             [0, 0, 15, 7, 0, 22, 18, 0],
             [0, 0, 0, 0, 22, 0, 0, 0],
             [15, 0, 0, 0, 18, 0, 0, 0],
             [0, 0, 10, 0, 0, 0, 0, 0]]

xCoord=[mylabel2[k][0] for k in sorted(mylabel2)]
yCoord=[mylabel2[k][1] for k in sorted(mylabel2)]
plt.plot(xCoord, yCoord, 'bo')
plt.axis([-1, 7, -1, 9])
for i in xrange(8):
    plt.text(xCoord[i]-0.5, yCoord[i], mylabel[i+1])
for i in xrange(8):
    for j in xrange(8):
        if Adj_Matrix[i][j]:
            plt.plot([xCoord[i], xCoord[j]],[yCoord[i], yCoord[j]], 'b')
#Dijkstra Algorithm
def dijkstra(graph,start,target):
    inf = reduce(lambda x,y: x+y,(i[1] for u in graph for i in graph[u]))
    dist = dict.fromkeys(graph,inf)
    prev = dict.fromkeys(graph)
    q = graph.keys()
    dist[start] = 0
    while q:
        u = min(q, key=lambda x: dist[x])
        q.remove(u)
        for v,w in graph[u]:
            alt = dist[u] + w
            if alt < dist[v]:
                dist[v] = alt
                prev[v] = u
    #”way”
    trav = []
    temp = target
    while temp != start:
        trav.append(prev[temp])
        temp = prev[temp]
    trav.reverse()
    trav.append(target)
    return " -> ".join(trav),dist[target]

graph = {
    'A' : [('B',20), ('G', 15)],
    'B' : [('A', 20),('C', 8), ('D', 9)],
    'C' : [('B', 8),('D', 6), ('E', 15), ('H', 10)],
    'D' : [('B', 9),('C', 6),('E', 7)],
    'E' : [('C', 15),('D', 7),('F', 22),('G', 18)],
    'F' : [('E', 22)],
    'G' : [('A', 15),('E', 18)],
    'H' : [('C', 10)]
    }
traverse, dist = dijkstra(graph,'F','H')
print traverse
#Drawing of coordinates
mydrawing = traverse.split('-> ')
plt.plot([ mylabel2[n.rstrip()][0] for n in mydrawing ],[ mylabel2[n.rstrip()][1] for n in mydrawing])
print "Distance:",dist
plt.show()

answered Mar 26, 2015 at 17:03

Nizam Mohamed

9,31026 silver badges33 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

Simon Hanks Over a year ago

Wow Nizam Mohamed, thanks so much. The code is much simpler and does exactly what I want. You saved me a lot, much appreciated.

Nizam Mohamed Over a year ago

@Simon Hanks but why F -> E -> D -> C -> H instead of F -> E -> C -> H? can you elaborate the algo?

Simon Hanks Over a year ago

F-> E-> D -> C -> H is 45 which is shorter than F -> E -> C -> H which is 47, when traversing from F -> H. Hence the algorithm is based on the cost of traversing and not the just the path.

Collectives™ on Stack Overflow

Dijkstra's algorithm in Python plotting path

1 Answer 1

3 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

3 Comments

Your Answer

Sign up or log in

Post as a guest

Related