# Numerical Solutions to the Variational Problems by [PERSON]'s Path-Finding Algorithm
## 4 Ray Tracing and Snell's Law
If the wave speed at vertices i and j are \(\mathrm{v_{i}}\) and \(\mathrm{v_{j}}\), respectively, the average wave speed along the joining edge can be estimated to be \(\left(\mathrm{v_{i}}+\mathrm{v_{j}}\right)/2\), and the weight can be defined as  
\[\mathrm{t_{ij}}=\frac{2\mathrm{s_{ij}}}{\mathrm{v_{i}}+\mathrm{v_{j}}}\;, \tag{12}\]  
where \(\mathrm{s_{ij}}\) is the Euclidian distance between vertices i and j. The total ToF can be estimated as  
\[\mathrm{t_{f}}=\sum_{\mathrm{path}}\mathrm{t_{ij}}\;. \tag{13}\]  
The summation is evaluated along the path from the starting to destination vertices. Figure 4 shows an example of the weight of an edge on the simple network in Figure 2. The ToF along the red path is, thus, \(\mathrm{t_{f}}=\mathrm{t_{ac}}+\mathrm{t_{cd}}+\mathrm{t_{db}}\), and the ToF along the blue path is \(\mathrm{t_{f}}=\mathrm{t_{ac}}+\mathrm{t_{ef}}+\mathrm{t_{fg}}+\mathrm{t_{ gh}}+\mathrm{t_{hb}}\). Note that the details of all edges are removed for the clarity of the figure. The final step is to apply [PERSON]'s algorithm to find the shortest path that minimizes the summation in Equation (13). Figure 5 shows the simulation result of the refraction between the mediums that \(\mathrm{v_{2}}/\mathrm{v_{1}}\)\(=1.500\), which resembles the refraction of light through the boundary of glass (lower medium 1) and air (upper medium 2). In the simulations, we use the 10 \(\times\) 10-unit square-lattice (\(\Delta x=\Delta y=1\)), with 10 sub-lattices on each plaquette side. The starting and destination points are the lower left vertex at the coordinate (0,0) and the upper right vertex at the coordinate (10,10), respectively. For clarity, we omit the details of the vertices and edges. The path obtained by [PERSON]'s algorithm is the red line. The blue line is the boundary of the two mediums, and the green line is the normal line. The wave speeds at the vertices below the boundary are set to be \(\mathrm{v_{1}}=\mathrm{c}/1.5\), and those on the boundary and above are \(\mathrm{v_{2}}=\mathrm{c}\). We can see that the algorithm gives the correct straight paths in each medium. The direction of the ray path changes only at the incident point on the boundary. In Figure 5, the coordinate of the refraction point (the black dot) is (3.1812,5); thus, \(\sin\theta_{2}/\sin\theta_{1}\)\(=1.502\), which agrees well with the prediction of [PERSON]'s law in Equations (10) and (11). When the incident angle of the light ray, traveling from the medium with higher to lower refractive indices, is approaching a critical angle, we will see the onset of the total internal reflection. This critical angle can be obtained from the relation \(\sin\theta_{1}=\mathrm{v_{1}}/\mathrm{v_{2}}\)[26]. In the case of glass-air refraction described above, we have \(\sin\theta_{1}\)\(=0.667\). Since the refracted  
Figure 4: An example of the designation of the weight of an edge connecting the vertices a and b is the ToF \(\mathrm{t_{cd}}\). The purple arrows are the velocity vector of the wave at vertices c and d, with wave speeds \(\mathrm{v_{c}}\) and \(\mathrm{v_{d}}\), respectively. The weight is defined as the ToF from vertices c to d along the straight edge, which can be estimated as the ratio of the Euclidian distance \(\mathrm{s_{cd}}\) and the average speed (\(\mathrm{v_{c}}+\mathrm{v_{d}}\))/2. The weights of the other edges can be defined similarly. angle is 90\({}^{\circ}\), we can simulate this phenomenon by placing the destination vertices on the boundary. Figure 6 shows the shortest path obtained by the [PERSON]'s algorithm. We place the starting vertex at the lower left corner of the lattice. The destination point is placed at the rightmost vertex on the boundary. In Figure 6, the coordinate of the refraction point (the black dot) is (4.4546, 5); thus, \(\sin\theta_{1}\)= 0.665, which agrees well with the theoretical prediction.