Алгоритм Дейкстры в пути построения Python

Мне нужно адаптировать алгоритм Дейкстры ниже, чтобы показать координаты кратчайшего пути.

Мне также нужно нарисовать путь, но у меня возникают проблемы с получением правильных координат для построения графика.

Я использую функцию mylabel2 для назначения координат, и я также хотел бы построить путь. Пожалуйста, смотрите в комментарии #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