Алгоритм алгоритма Дейкстры в Python

Question

У меня проблемы с алгоритмом Дейкстры в python. Я понимаю, как работает алгоритм Дейкстры, но я не настолько хорош в преобразовании его в код. Есть ли способ добавить узлы пути и распечатать их. Я продолжаю идти по пути. Спасибо.

import heapq 
import sys 

x = raw_input() 
y = raw_input() 
class Graph: 

def __init__(self): 
    self.vertices = {} 

def add_vertex(self, name, edges): 
    self.vertices[name] = edges 

def shortest_path(self, start, finish): 
    distances = {} # Distance from start to node 
    previous = {} # Previous node in optimal path from source 
    nodes = [] # Priority queue of all nodes in Graph 

    for vertex in self.vertices: 
     if vertex == start: # Set root node as distance of 0 
      distances[vertex] = 0 
      heapq.heappush(nodes, [0, vertex]) 
     else: 
      distances[vertex] = sys.maxint 
      heapq.heappush(nodes, [sys.maxint, vertex]) 
     previous[vertex] = None 

    while nodes: 
     smallest = heapq.heappop(nodes)[1] # Vertex in nodes with smallest distance in distances 
     if smallest == finish: # If the closest node is our target we're done so print the path 
      path = [] 
      while previous[smallest]: # Traverse through nodes til we reach the root which is 0 
       path.append(smallest) 
       smallest = previous[smallest] 
      return path 
     if distances[smallest] == sys.maxint: # All remaining vertices are inaccessible from source 
      break 

     for neighbor in self.vertices[smallest]: # Look at all the nodes that this vertex is attached to 
      alt = distances[smallest] + self.vertices[smallest][neighbor] # Alternative path distance 
      if alt < distances[neighbor]: # If there is a new shortest path update our priority queue (relax) 
       distances[neighbor] = alt 
       previous[neighbor] = smallest 
       for n in nodes: 
        if n[1] == neighbor: 
         n[0] = alt 
         break 
       heapq.heapify(nodes) 
    return distances 

def __str__(self): 
    return str(self.vertices) 

g = Graph() 
g.add_vertex('A', {'B': 7, 'C': 8}) 
g.add_vertex('B', {'A': 7, 'F': 2}) 
g.add_vertex('C', {'A': 8, 'F': 6, 'G': 4}) 
g.add_vertex('D', {'F': 8}) 
g.add_vertex('E', {'H': 1}) 
g.add_vertex('F', {'B': 2, 'C': 6, 'D': 8, 'G': 9, 'H': 3}) 
g.add_vertex('G', {'C': 4, 'F': 9}) 
g.add_vertex('H', {'E': 1, 'F': 3}) 
print g.shortest_path(x, y) 

Answer 1

Так что я смог выяснить, как использовать алгоритм. Вот что я придумал.

import heapq 

x = raw_input() 
y = raw_input() 

def shortestPath(start, end): 
queue,seen = [(0, start, [])], set() 
while True: 
    (cost, v, path) = heapq.heappop(queue) 
    if v not in seen: 
     path = path + [v] 
     seen.add(v) 
     if v == end: 
      return cost, path 
     for (next, c) in graph[v].iteritems(): 
      heapq.heappush(queue, (cost + c, next, path)) 

graph = { 
'a': {'w': 14, 'x': 7, 'y': 9}, 
'b': {'w': 9, 'z': 6}, 
'w': {'a': 14, 'b': 9, 'y': 2}, 
'x': {'a': 7, 'y': 10, 'z': 15}, 
'y': {'a': 9, 'w': 2, 'x': 10, 'z': 11}, 
'z': {'b': 6, 'x': 15, 'y': 11}, 
} 
cost, path = shortestPath(x, y) 
print cost, path