python- Catalogue of mathematical modeling series articles

`

： The fifth chapter is 4 Little topic

subject

4 A company is 6 Cities c1,c2,c3…c6 There are branches in , Known cities ci To cj(I,j=1,2,3,…6) The connection case and the cost are listed in the following weighted adjacency matrix C in .
C=[[0,50,-,40,25,10],
[50,0,15,20,-,25],
[-,15,0,10,20,-],
[40,20,10,0,10,25],
[25,-,20,10,0,55],
[10,25,-,25,55,0]]
- Express no straight path

（1） Judge whether the adjacency matrix is a directed or undirected graph ?

According to the formula ,ai j ={wij,(vi,vj) Belong to E,wij Is the weight
1,vi,vj adjacent
0 vi,vj Not adjacent ). Judge the symmetry of the matrix, which is an undirected weighted graph

（2） Draw the corresponding weighting graph ？

（3） Seeking from the city C1 set out , The minimum cost route and cost to other cities ？
analysis ： This problem is the minimum path weight problem from the fixed point to the other points ,Dijkstra Algorithm

The code is as follows （ Example ）：

from importlib.resources import path
import networkx as nx
import numpy as np
L=[(1,2,50),(1,4,40),(1,5,25),(1,6,10),
(2,3,15),(2,4,20),(2,6,25),
(3,4,10),(3,5,20),
(4,5,10),(4,6,25),
(5,6,55),]
G=nx.Graph()
G.add_weighted_edges_from(L)
path=nx.shortest_path(G,1,weight='weight')
cost=nx.shortest_path_length(G,1,weight='weight')
print('path:',path);print('cost:',cost)
for i in range(1,7):
    print('c1 to c{} short length:'.format(i),path[i])

Calculated value

path: {1: [1], 2: [1, 6, 2], 4: [1, 6, 4], 5: [1, 5], 6: [1, 6], 3: [1, 5, 3]}
cost: {1: 0, 6: 10, 5: 25, 2: 35, 4: 35, 3: 45}
c1 to c1 short length: [1]
c1 to c2 short length: [1, 6, 2]
c1 to c3 short length: [1, 5, 3]
c1 to c4 short length: [1, 6, 4]
c1 to c5 short length: [1, 5]
c1 to c6 short length: [1, 6]