Matrix to Tree Algorithm
The code is clean, modular and readable. You could try to work with generators
to make the calculations lazy.

I think the namedtuple are a better choice than your dict approach, something like:

Node = collections.namedtuple('Node', ['name', 'distance', 'children'])


You can look into the way a functional language like Hskell or Clojure represents trees. It is weird that you mark the leaves of your tree by empty dicts and replace them with the calculated distance.


PEP8:


Use 4 spaces per indentation level.
Separate top-level function and class definitions with two blank lines.

set_start(): Why not just return tree[start]?
set_end():


tree[end] can result in a KeyError
Why the if len(nodes) &gt; 1?

if end in tree:
    del tree[end]
for child in tree.values():
    set_end(child, end)
return tree


node_distance(): This is an internal function and can be inlined in map_tree().
Please do not place code on module level, but wrap it in a main() or test() function.

nodes = [key for key in x.keys()] can be simplified to nodes = list(x.keys()).