Graph is a connection of nodes with edges. Node is sometimes called as vertex, and edges is sometimes called branch.
An example graph is shown in Figure 1. In the figure, nodes are represened by letters and circles, and edges are represented by lines coneecting nodes. The number near the edge is the weight of the edge.
Figure 1: Example of Graph 
The graph of Figure 1 can be represented by the adjacency matrix in Table 1. Here, each element of the matrix is its weight if there is an edge between the nodes, or "" if there is none. We also assume that the weight between the same nodes is 0.
Table1: Adjacency Matrix  

A number of cities and the road distances connecting them are given. Write a program that finds the shortest route from the starting city to the destination city.
$N$ $R$
$A_1$ $B_1$ $L_1$
$A_2$ $B_2$ $L_2$
$\quad\cdots$
$A_R$ $B_R$ $L_R$
$S$ $D$
The first line contains 2 integers $N$ and $R$ which represent the number of cities, and the number of roads connecting those cities, respectively.
$1 \leqq N \leqq 100$
Each of the $R$ lines after the second line contains 3 integers, $A_i$, $B_i$, and $L_i$
$~~$ ($1 \leqq i \leqq R$).
$A_i$ and $B_i$ represent both ends of the $i$th road, and
$L_i$ represents the distance of the road.
$0 \leqq A_i \leqq N1$
$0 \leqq B_i \leqq N1$
The last line contains 2 integers, $S$, $D$ which represent the starting city and the destination city, respectively.
$0 \leqq S \leqq N1$
$0 \leqq D \leqq N1$
If the shortest path is found, print it as follows.
On the first line, print an integer representing the distance of the shortest path. And on the next line, print the cities along the shortest path from the starting city to the destination city, with a space between them.
If there are multiple shortest path, one of them should be the answere.
If there is no shortest path, print "no route".
Dijkstra's is an algorithm that finds the shortest path to each node one bye one from the vicinity of the starting node, and gradually expands the range. Can be used when all edge weights are nonnegative ($\geqq 0$).
Let's find the shortest path from node a to node h.  
Assume that the shortest distance of each node is "unfixed"
and its value is infinity ($\infty$). Then, assume the shortest distance of the starting node (a) is 0.  
Select the shortest node
(a marked with ☆)
among the "unfixed" nodes. The shortest distance of the selected node (a marked with ☆) is "fixed" to the current value (0). The "fixed" node is separated from "unfixed" nodes by a red boundary line (frontier).  
Calculate the distance of each node (b, c, d ), if and only if the node is "directly connected" from the most recently fixed node (a with ☆), and its "shortest distance" is "unfixed". If the result is less than current value, update it (b → 1, c → 7, d → 2). Edges that update the shortest distance of unfixed nodes across the boundary are expressed by light blue arrows.  
Select the shortest node
(b marked with ☆)
among the "unfixed" nodes. The shortest distance of the selected node (b marked with ☆) is "fixed" to the current value (1). If there are multiple nodes with the shortest distance value, it doesn't matter which one you choose.  
Calculate the distance of each node (e, f), if and only if the node is "directly connected" from the most recently fixed node (b with ☆), and its "shortest distance" is "unfixed". If the result is less than current value, update it (e → 3, f → 5).  
Select the shortest node
(d marked with ☆)
among the "unfixed" nodes. The shortest distance of the selected node (d marked with ☆) is "fixed" to the current value (2).  
Calculate the distance of node (g), if and only if the node is "directly connected" from the most recently fixed node (d with ☆), and its "shortest distance" is "unfixed". If the result is less than current value, update it (g → 7).  
Select the shortest node
(e marked with ☆)
among the "unfixed" nodes. The shortest distance of the selected node (e marked with ☆) is "fixed" to the current value (3).  
Calculate the distance of node (f), if and only if the node is "directly connected" from the most recently fixed node (e with ☆), and its "shortest distance" is "unfixed". If the result is less than current value, update it (f → 4).  
Select the shortest node
(f marked with ☆)
among the "unfixed" nodes. The shortest distance of the selected node (f marked with ☆) is "fixed" to the current value (4).  
Calculate the distance of each node (c, h), if and only if the node is "directly connected" from the most recently fixed node (f with ☆), and its "shortest distance" is "unfixed". If the result is less than current value, update it (c → 6, h → 10).  
Select the shortest node
(c marked with ☆)
among the "unfixed" nodes. The shortest distance of the selected node (c marked with ☆) is "fixed" to the current value (6).  
Calculate the distance of each node (g), if and only if the node is "directly connected" from the most recently fixed node (g with ☆), and its "shortest distance" is "unfixed". The shortest distance of g is not updated, becase the computed result(9 is not less than the current value (7).  
Select the shortest node
(g marked with ☆)
among the "unfixed" nodes. The shortest distance of the selected node (g marked with ☆) is "fixed" to the current value (7).  
Calculate the distance of each node (h), if and only if the node is "directly connected" from the most recently fixed node (g with ☆), and its "shortest distance" is "unfixed". If the result is less than current value, update it (h → 9).  
Select the shortest node
(h marked with ☆)
among the "unfixed" nodes. The shortest distance of the selected node (h marked with ☆) is "fixed" to the current value (9).  
The shortest distance (9) from a to h and shortest path (a → d → g → h) are found. 
Consider the example below to explain why Dijkstra's algorithm works correctly.
The above figure is immediately after "node b is fixed and the estimated distance of nodes e and f are updated".
There are 3 types of node status.
Dijkstra's algorithm asserts that "the shortest node (d) among the unfixed nodes can be fixed with the current value (2)". And it is clear from the fact that "all edge weights are nonnegative" in the graph Dijkstra's targets.
Consider the "unfixed" nodes on the right side of the boundary line. The "unfixed but estimated" nodes (c, d, e, f) hold the shortest distance via the current "fixed" nodes (a, b). Then, the shortest node (d) among the "unfixed but estimated" nodes (c, d, e, f) has the shortest distance even including "unfixed and infinity ($\infty$)" nodes (g, h). Because all edge weights are nonnegative, going to d through the current "unfixed" nodes is far.
In other words, the shortest distance from a to d is currently estimated correctly and can be fixed at the current value.
Thinking like this, we can see that Dijkstra's algorithm claims something very obvious.
It is important to focus on the boundary line (frontier) between the "fixed" nodes and "unfixed" nodes. The "unfixed but estimated" nodes are connected directly with some "fixed" nodes. The shortest "unfixed but estimated" node (d) cannot be shorter via other unfixed nodes. Therefore, its true minimum value has already been found.
The shortest distance of one node is fixed in one loop. Since this is repeated for $n$ nodes, the complexity of this iterative operation is $O(n)$.
Once the shortest distance to a node is fixed, update the distance estimates for each node connected to that node. The maximum number nodes connected to a node is $n1$, so the complexity of this operation is $O(n)$.
So the total complexity is $O(n) \times O(n) = O(n^2)$.
In the following graph, answer the distance of the shortest route from node a to node i.
a: Start nodeRun dijkstraPath.py on the following data and measure the computation time.
dijkstra.py 

Execution Log of dijkstra.py 

When updating the distance to a node, record the previous node in via[]. Once the shortest distance to the destination node is fixed, the shortest path can be found by tracing the transit nodes in reverse order.
dijkstraPath.py 

Execution log of dijkstraPath.py 

The slow Java program that simply implements Dijkstra's algorithm is as follows.
Dijkstra.java 

Execution log of Dijkstra.java 

In "Dijkstra.java", node connections are kept in memory as a 2dimensional array, so large data may cause an OutofMemory Exception and terminate program execution. In that case, expand the heap memory of the java virtual machine with the Xms option of java command.
route13.data(part) 

Expand heap memory when Dijkstra.java runs 

Let's change the program that is also shows the shortest path.
Record the previous node in via[] when updating the shortest distance for each node.
Change DijkstraPath.java Output of " diff c Dijkstra.java DijkstraPath.java " 

Execution log of DijkstraPath.java 

For a sparse graph with many nodes, such as route13.data, try expanding the head memory when running "DijkstraPath.java". In some environment, it can be calculated, albeit slowly.
Execution time of DijkstraPath.java for route13.data CPU:Ryzen 5900HX, Memory: DDR4 32GB 

In Dijkstra's algorithm, when dealing with sparse graphs (that is, graphs with fewer edges than the number of nodes), it is expected that the calculation speed will be increased by the following measures. Although the complexity order does not change.
The computational complexity of Priority First Seach is:
$\quad$ "for each of $n$ nodes"
$\quad$$\quad$ "to retrieve the shortest node from the heap"
$\quad$$\quad$ and
$\quad$$\quad$ "to update the distance of nodes directly connected by the most recently fixed node",
where
"for each of $n$ nodes" : $O(n)$
"to retrieve the shortest node from the heap": $O(\log n)$
"to update the distance of nodes directly connected by most recently fixed node": $O(n)$ ← can be regarded as a constant for sparse graphs.
The practical execution time is expected to be
$O(n) \times O( \log n + \mbox{Constant}) = O(n \log n)$ .
Priority Queue is a data structure called a "heap" that allows access to specific data in $O(\log n)$.
The Java program of Priority First Search written using the PriorityQueue
class is as follows.
PFSPath.java 

Execution log of PFSPath.java 

Let's run "PFSPath.java" against data representing a sparse graph with many nodes, say "route13.data" Unlike the case of "DijkstraPath.java", the answer can be obtained with "small memory consumption" and "fast".
Execution time of PFSPath.java for route13.data CPU:Ryzen 5900HX, Memory: DDR4 32GB 

Dijkstra's algorithm cannot solve when there are edges with negative weights in the graph. In such cases, use the BellmanFord algorithm to solve.