Weighted graph from a matrix (list-of-lists)
Well, both node_name and make_graph can be a bit smaller, yes.

def node_name(row_index, col_index):
    return "{},{}".format(row_index, col_index)


format will do the string conversion automatically, no need to call str.

I'd also give everything a bit more space to make it more readable.

def make_graph(matrix):
    graph = {}

    width, height = len(matrix[0]), len(matrix)

    columns = range(width)
    for rowindex in range(height):
        for colindex in columns:
            graph[node_name(rowindex, colindex)] = x = {}

            # Up
            if rowindex &gt; 0:
                x[node_name(rowindex - 1, colindex)] = matrix[rowindex - 1][colindex]
            # Down
            if rowindex &lt; height - 1:
                x[node_name(rowindex + 1, colindex)] = matrix[rowindex + 1][colindex]
            # Left
            if colindex &gt; 0:
                x[node_name(rowindex, colindex - 1)] = matrix[rowindex][colindex - 1]
            # Right
            if colindex &lt; width - 1:
                x[node_name(rowindex, colindex + 1)] = matrix[rowindex][colindex + 1]

    return graph


Except caching more things this would look okay to me.  Relying a
rectangular matrix seems obvious to me, so width and height can be
precomputed.  Using range also makes it more clear that you really
want the coordinates, not the row or column values.

In the interest of verbosity I'd also just i and j for indexes, but
that's your choice obviously.

Also, you know that {(1, 1): 1} works, right?  Because there doesn't
seem to be a pressing reason to use node_name at all.  In contrast to
a list a tuple is immutable and can be used as a dictionary key, see
also this wiki page for a more thorough discussion on that.