1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
|
# Example of a shortest path network flow in a graph
# Shows integration of highspy with networkx
import highspy
import networkx as nx
orig, dest = ('A', 'D')
# create directed graph with edge weights (distances)
G = nx.DiGraph()
G.add_weighted_edges_from([('A', 'B', 2.0), ('B', 'C', 3.0), ('A', 'C', 1.5), ('B', 'D', 2.5), ('C', 'D', 1.0)])
h = highspy.Highs()
h.silent()
x = h.addBinaries(G.edges, obj=nx.get_edge_attributes(G, 'weight'))
# add flow conservation constraints
# { 1 if n = orig
# sum(out) - sum(in) = { -1 if n = dest
# { 0 otherwise
rhs = lambda n: 1 if n == orig else -1 if n == dest else 0
flow = lambda E: h.qsum((x[e] for e in E))
h.addConstrs(flow(G.out_edges(n)) - flow(G.in_edges(n)) == rhs(n) for n in G.nodes)
h.minimize()
# Print the solution
print('Shortest path from', orig, 'to', dest, 'is: ', end = '')
sol = h.vals(x)
n = orig
while n != dest:
print(n, end=' ')
n = next(e[1] for e in G.out_edges(n) if sol[e] > 0.5)
print(dest)
|
