Matrix to Tree Algorithm

The code takes a matrix and turns it into a tree of all the possible combinations. It then "maps" the tree by setting the value of the ending nodes to the total distance of the nodes from beginning node to ending node.

It seems to work fairly well but I've got a couple questions:

1. Is a Python dict the best way to represent a tree?
2. Any ways to simplify, speed up, or otherwise make it more clean and legible?

Keep in mind I'll need to sort the set so I can display the most attractive routes.

You can find the code on my GitHub page (starts at line 61).

def matrix_to_tree(nodes):
  """
  Creates a tree of all possible combinations of
  provided nodes in dict format
  """
  tree = {}
  for node in nodes:
    children = nodes[:]
    children.remove(node)
    tree[node] = matrix_to_tree(children)
  return tree

def set_start(tree, start):
  """
  Removes extraneous starting nodes if only one
  starting location is desired.
  """
  tree = tree[start]
  return tree

def set_end(tree, end):
  """
  Removes ending nodes when they are not the
  last node of the branch.  Used when one
  ending location is desired.
  """
  if tree[end]:
    del tree[end]
  nodes = tree.keys()
  if len(nodes) > 1:
    for node in nodes:
      set_end(tree[node], end)
  return tree

def map_tree(tree, matrix, start, distance=0):
  """
  Maps the distance from the root to each
  ending node.
  """
  for node in tree:
    new_distance = distance + node_distance(matrix, start, node)
    if tree[node]:
      map_tree(tree[node], matrix, node, new_distance)
    else:
      tree[node] = new_distance
  return tree

def node_distance(matrix, start, end):
  """
  Searches a matrix for the value of two
  points.
  """
  return matrix[start][end]

nodes = [key for key in x.keys()]
a = matrix_to_tree(nodes)
b = set_start(a, 'A')
c = set_end(b, 'G')
d = map_tree(c, x, 'A')
print(d)

Input example:

{ A: {B:1, C:2}, B: {A:1, C:3}, C: {A:2, B:3}, }

Output example:

# 'A' being the root node with no ending node specified
{
    A: {B:{C:4}, C:{B:5}},
}