python - Dijkstra 算法在 Python 中的帮助

Question

我在 python 中遇到了 Dijkstra 算法的问题。我了解 Dijkstra 算法的工作原理，但我不太擅长将其转换为代码。有没有办法添加路径的节点并将它们打印出来。我一直在寻找路径。谢谢。

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