Firstly, we have to define a structure to store the graph. There are many ways a graph can be represented for performing computations. The simplest way, for our purposes, is to use a dictionary whose keys are the graph nodes. The value associated with each key contains another dictionary, representing the edges starting from that node and its corresponding weight. For instance, the graph we have been studying in this chapter can be written as follows:
G = {
'A': {'B': 10, 'C': 33, 'D': 35},
'B': {'A': 10, 'C': 20},
'C': {'A': 20, 'B': 33, 'D': 28, 'E': 6},
'D': {'A': 35, 'C': 28, 'E': 40},
'E': {'C': 6, 'D' : 40},
}
This means that vertex A is connected to three other vertices:
- B, with weight 10
- C, with weight 33
- D, with weight 35...
