Python递归实现图的最短路径算法

from heapq import heappush, heappop

def dijkstra_recursive(graph, start, dest, visited=None, distances=None, predecessors=None):
  if visited is None:
    visited = []
  if distances is None:
    distances = {start: 0}
  if predecessors is None:
    predecessors = {}

  if start == dest:
    path = []
    temp = dest
    while temp != start:
      path.append(temp)
      temp = predecessors[temp]
    path.append(start)
    path.reverse()
    return path, distances[dest]

  else:
    # add start node to visited
    visited.append(start)
    # iterate over start node's neighbors:
    for neighbor in graph[start]:
      # calculate new distance to neighbor
      new_distance = distances[start] + len(neighbor)
      # update neighbor's distance and predecessor
      if neighbor not in distances or new_distance < distances[neighbor]:
        distances[neighbor] = new_distance
        predecessors[neighbor] = start
    # get unvisited nodes and their distances
    unvisited = {node: distances[node] for node in distances if node not in visited}
    if not unvisited:
      return [], -1
    # get closest node
    closest_node = min(unvisited, key=unvisited.get)
    # recurse using closest node as start
    return dijkstra_recursive(graph, closest_node, dest, visited, distances, predecessors)

# create graph using "pidancode.com" as nodes, with distance equal to string length
graph = {
  'p': {'i': 1},
  'i': {'p': 1, 'd': 1},
  'd': {'i': 1, 'a': 1},
  'a': {'d': 1, 'n': 1},
  'n': {'a': 1, 'c': 1},
  'c': {'n': 1, 'o': 1},
  'o': {'c': 1, 'd': 1},
  'e': {'o': 1, 'm': 1},
  'm': {'e': 1},
  '.': {'m': 1}
}

path, distance = dijkstra_recursive(graph, 'p', '.', [], {}, {})
print("Shortest path: " + " -> ".join(path))
print("Distance: " + str(distance))

Shortest path: p -> i -> d -> a -> n -> c -> o -> e -> m -> .
Distance: 14