Algorithms For Dummies

  Relying on Dynamic Programming 

     313

Graph = nx.Graph()

Graph.add_nodes_from(range(D.shape[0]))

for i in range(D.shape[0]):

    for j in range(D.shape[0]):

        Graph.add_edge(i,j,weight=D[i,j])

np.random.seed(2)

pos=nx.shell_layout(Graph)

nx.draw(Graph, pos, with_labels=True)

labels = nx.get_edge_attributes(Graph,'weight')

nx.draw_networkx_edge_labels(Graph,pos,

                             edge_labels=labels)

plt.show()

After defining the 

D

 (distance) matrix, the example tests the first, simplest solu-

tion to determine the shortest tour starting and ending from city zero. This solu-

tion relies on brute force, which generates all the possible order permutations 

between the cities, leaving out zero. The distance from zero to the first city and 

from the last city of the tour to zero is added after the total distance of each 

 solution is calculated. When all the solutions are available, you simply choose the 

shortest.

from itertools import permutations

best_solution = [None, np.sum(D)]

for solution in list(permutations(range(1,D.shape[0]))):

FIGURE 16-1: 

Cities 

represented 

as nodes in a 

weighted graph.

---

314

 

   

  PART 5