Algorithms For Dummies

  Reconnecting the Dots 

     185

nx.draw_networkx_edge_labels(Graph, pos,

                             edge_labels=labels)

nx.draw_networkx(Graph,pos)

plt.show()

Figure 9-2 shows that all edges have a value now. This value can represent some-

thing  like  time,  fuel,  or  money.  Weighted  graphs  can  represent  many  possible 

optimization  problems  that  occur  in  geographical  space  (such  as  movement 

between cities) because they represent situations in which you can come and go 

from a vertex.

Interestingly, all edges have positive weights in this example. However, weighted 

graphs can have negative weights on some edges. Many situations take advantage 

of negative edges. For instance, they’re useful when you can both gain and lose 

from moving between vertexes, such as gaining or losing money when transport-

ing or trading goods, or releasing energy in a chemical process.

Not all algorithms are well suited for handling negative edges. It’s important to 

note those that can work with only positive weights.