Algorithms For Dummies

  Reconnecting the Dots 

     193

Other algorithms can solve the shortest-path problem. The Bellman-Ford and 

Floyd-Warshall are more complex but can handle graphs with negative weights. 

(Negative weights can represent some problems better.) Both algorithms are 

beyond the scope of this book, but the site at 

https://www.hackerearth.com/ 

ja/practice/algorithms/graphs/shortest-path-algorithms/tutorial/

 pro-

vides additional information about them. Because the shortest-path problem 

involves graphs that are both weighted and directed, the example graph requires 

another update before proceeding (you can see the result in Figure 9-3). (You can 

find this code in the 

A4D; 09; Shortest Path.ipynb file

 on the Dummies site 

as part of the downloadable code; see the Introduction for details.)

import numpy as np

import networkx as nx

import matplotlib.pyplot as plt

%matplotlib inline

graph = {'A': {'B':2, 'C':3},

         'B': {'C':2, 'D':2},

         'C': {'D':3, 'E':2},

         'D': {'F':3},

         'E': {'D':1,'F':1},

         'F': {}}

Graph = nx.DiGraph()

for node in graph:

    Graph.add_nodes_from(node)

    for edge, weight in graph[node].items():

        Graph.add_edge(node,edge, weight=weight)

pos = { 'A': [0.00, 0.50], 'B': [0.25, 0.75],

        'C': [0.25, 0.25], 'D': [0.75, 0.75],

        'E': [0.75, 0.25], 'F': [1.00, 0.50]}

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

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

nx.draw_networkx_edge_labels(Graph, pos,

                             edge_labels=labels)

nx.draw_networkx(Graph,pos)

plt.show()

---

194