pythongraphnetworkx

return path and total weight from graph

let us suppose that we have following graph : enter image description here

implementation of this graph is done using following code :

import networkx as nx
import matplotlib.pyplot as plt
G =nx.DiGraph()
edges = [("A", "B", 4), ("A", "C", 2), ("B", "C", 5), ("B", "D", 10),
         ("C", "E", 3), ("E", "D", 4), ("D", "F", 11)]
G.add_weighted_edges_from(edges)
pos=nx.spring_layout(G) # pos = nx.nx_agraph.graphviz_layout(G)
nx.draw_networkx(G,pos)
labels = nx.get_edge_attributes(G,'weight')
nx.draw_networkx_edge_labels(G,pos,edge_labels=labels)
plt.show()
# print(list(nx.all_shortest_paths(G,source='A',target='F')))

result is : enter image description here

from source A to F minimum distance is 20, here is all info about path and their total distances :

A-B-D-F   :4+10+11=25
A-C-E-D-F  :2+3+4+11=20
A-B-C-E-D-F  : 4+5+3+4+11=27

my question is : how can i show all route and total distance? if we calculate only single route ,we get :

print(nx.dijkstra_path(G,source='A',target='F'))

result is :

['A', 'C', 'E', 'D', 'F']

and total distance :

print(nx.dijkstra_path_length(G,source='A',target='F'))

result is 20, what about all route from A to F? and their total distance?

Solution

  • Use one of the built-in iterators:

    import networkx as nx

G = nx.DiGraph()
G.add_weighted_edges_from([
    ('A', 'B',  4),
    ('A', 'C',  2),
    ('B', 'C',  5),
    ('B', 'D', 10),
    ('C', 'E',  3),
    ('E', 'D',  4),
    ('D', 'F', 11),
])

for path in nx.all_simple_paths(G, source='A', target='F'):
    weight = nx.path_weight(G, path, 'weight')
    print(f'Length {len(path)}, weight {weight}: {"".join(path)}')

    Length 6, weight 27: ABCEDF
Length 4, weight 25: ABDF
Length 5, weight 20: ACEDF