Scientific Calculations with Julia/Shortest Path

Scientific Calculations with Julia Shortest Path Cost Minimization Traveling Salesman In graph theory, the shortest path between two vertices (or nodes) of a graph is the path that connects the vertices and minimizes the sum of the costs associated with traversing each edge (or edge). Suppose we want to travel from position 1 to position 6, minimizing the total distance to travel. First, we need to construct the adjacency matrix: adjacency_matrix = [ 0 2 4 0 0 0; 0 0 1 7 0 0; 0 0 0 0 3 0; 0 0 0 0 0 1; 0 0 0 2 0 5; 0 0 0 0 0 0 ]; In practice, from position 1 to position 2 there are 2km, so the element (1,2) of the matrix has the value 2; from position 1 to position 3 there are 4km, so the element (1,3) of the matrix has the value 4; and so on, the adjacency matrix is ​​constructed... At this point, you need to install the Graphs, GraphPlot, and DataStructures libraries and construct the graph with the adjacency matrix: using Graphs G = SimpleDiGraph{Int16}(adjacency_matrix) This results in a directed graph with 6 vertices and 8 arrows. The graph's arrows are displayed: path = collect(edges(G)) 8-element Vector{Graphs.SimpleGraphs.SimpleEdge{Int16}}: Edge 1 => 2 Edge 1 => 3 Edge 2 => 3 Edge 2 => 4 Edge 3 => 5 Edge 4 => 6 Edge 5 => 4 Edge 5 => 6 The costs of each arrow, i.e., the kilometers from one position to another, are established using Julia's "SortedDict" data structure: using DataStructures edgelabels = SortedDict( (1,2)=>2, (1,3)=>4, (2,3)=>1, (2,4)=>7, (2,5)=>3, (4,6)=>1, (5,4)=>2, (5,6)=>5 ) Display the graph: using GraphPlot nvertices = nv(G) # number of vertices gplot(G, nodelabel=1:nvertices, edgelabel=values(edgelabels)) thumb|center|500px Apply the Dijkstra algorithm to find the shortest path from vertex 1 to vertex 6: path = enumerate_paths(dijkstra_shortest_paths(G,1),6) 4-element Vector{Int64}: 1 2 4 6 The shortest path is 1-->2-->4-->6 with a total cost of 10 km.