Python Shortest Path & Tuples

ShortestPath.py

neighbours = {
    "A":{"B":3,"C":4},
    "B":{"D":2},
    "C":{"D":1,"E":1,"F":6},
    "D":{"H":1},
    "E":{"H":7},
    "F":{"G":1},
    "G":{},
    "H":{"G":3}
}

def FindShortestPath(begin, end):

  if begin == end:
    return 1, [end]

  best_cost = 1e99
  best_path = []

  for ne in neighbours[begin]:
    (cost, path) = FindShortestPath(ne, end)

    # This is weird:
    # Pull the cost value out of the inner map which is inside the neighbours map
    cost += neighbours[begin][ne]

    path.insert(0, begin)

    if cost < best_cost:
      best_cost = cost
      best_path = path

  return best_cost, best_path


(cost, path) = FindShortestPath("A", "G")

print "cost: %d" % cost
print "Best path is", path