Calcoli scientifici con Julia/Cammino minimo

Nella teoria dei grafi, il cammino minimo (o shortest path) tra due vertici (o nodi) di un grafo è quel percorso che collega i suddetti vertici e che minimizza la somma dei costi associati all'attraversamento di ciascun arco (o lato). Supponiamo di voler raggiungere da una posizione 1, una posizione 6 minimizzando i km complessivi da percorrere. Innanzitutto occorre costruire la matrice delle adiacenze:

matrice_adiacenza = [
          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 pratica dalla posizione 1 alla posizione 2 ci sono 2Km quindi l'elemento (1,2) della matrice ha valore 2, dalla posizione 1 alla posizione 3 ci sono 4Km quindi l'elemento (1,3) della matrice ha valore 4 e così via si costruisce la matrice delle adiacenze...

A questo punto occorre installare le librerie Graphs, GraphPlot e DataStructures e costruire il grafo con la matrice di adiacenze:

using Graphs
G = SimpleDiGraph{Int16}(matrice_adiacenza)

si ottiene in tal modo un grafo orientato con 6 vertici e 8 frecce. Si visualizzano le frecce del grafo :

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

Si stabiliscono i costi di ciascuna freccia cioè i km da una posizione ad un'altra mediante la struttura dati "SortedDict" di Julia :

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
)

Si visualizza il grafo :

using GraphPlot
nvertices = nv(G) # number of vertices

gplot(G, nodelabel=1:nvertices, edgelabel=values(edgelabels))

Si applica l'algoritmo dijkstra per trovare il percorso minimo dal vertice 1 al vertice 6:

path = enumerate_paths(dijkstra_shortest_paths(G,1),6)

4-element Vector{Int64}:
1
2
4
6

Il cammino minimo è 1-->2-->4-->6 con un costo complessivo di 10 Km