Return to Answer

Here are two ways you could represent a graph with weighted edges in Python:

1. Represent a graph as a mapping from a node \$n\$ to a mapping from neighbouring node \$m\$ to the weight \$w\$ of the edge from \$n\$ to \$m\$:

    graph = {
    0: {2: 4, 4: 60, 3: 23},
    1: {},
    2: {3: 4},
    3: {1: 10},
    4: {2: 15},
    }
   

2. Represent a graph as a pair of mappings: one from a node \$n\$ to a list of its neighbouring nodes, and the order from pairs of nodes \$n, m\$ to the weight \$w\$ of the edge from \$n\$ to \$m\$:

    graph = {
    0: [2, 4, 3],
    1: [],
    2: [3],
    3: [1],
    4: [2],
    }
    weights = {
    (0, 2): 4,
    (0, 4): 60,
    (0, 3): 23,
    (2, 3): 4,
    (3, 1): 10,
    (4, 2): 15,
    }
   

Either of these representations should work fine. Representation (2) would be good if you need to iterate over all the edges at some point in your algorithm. Representation (1) is the simplest and probably best if you have no special requirements.

Here are two ways you could represent a graph with weighted edges in Python:

1. Represent a graph as a mapping from a node \$n\$ to a mapping from neighbouring node \$m\$ to the weight \$w\$ of the edge from \$n\$ to \$m\$:

    graph = {
    0: {2: 4, 4: 60, 3: 23},
    1: {},
    2: {3: 4},
    3: {1: 10},
    4: {2: 15},
    }
   

2. Represent a graph as a pair of mappings: one from a node \$n\$ to a list of its neighbouring nodes, and the other from pairs of nodes \$n, m\$ to the weight \$w\$ of the edge from \$n\$ to \$m\$:

    graph = {
    0: [2, 4, 3],
    1: [],
    2: [3],
    3: [1],
    4: [2],
    }
    weights = {
    (0, 2): 4,
    (0, 4): 60,
    (0, 3): 23,
    (2, 3): 4,
    (3, 1): 10,
    (4, 2): 15,
    }
   

Either of these representations should work fine. Representation (2) would be good if you need to iterate over all the edges at some point in your algorithm. Representation (1) is the simplest and probably best if you have no special requirements.

Answers to comments

1. You don't even need .keys() — in Python, iterating over a dictionary yields its keys, so you can write:

    for m in graph[n]:
    # m is a neighbour of n
   

2. Yes, defaultdict is a useful technique for building graphs. In representation (1) you'd start with:

    graph = defaultdict(dict)
   

and then add an edge from \$n\$ to \$m\$ with weight \$w\$ by writing:

 graph[n][m] = w

In representation (2) you'd start with:

 graph = defaultdict(list)
 edges = {}

and then add an edge from \$n\$ to \$m\$ with weight \$w\$ by writing:

 graph[n].append(m)
 edges[n, m] = w