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

Question

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

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

Я использую функцию 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 

Answer 1

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