# Near-Optimal Weather Routing by Using Improved A* Algorithm
## 2 Routing Algorithms
### \(A^{*}\) Algorithm  
The Bellman Ford algorithm calculates all pairs of paths leading to multiple sources, it can be advantageous in the case of an internet network that delivers information from a single source to many users, but it is inefficient for ship route optimization with single source-single destination. Similarly, as described above, the Dijkstra algorithm is not quite efficient for dense distance graphs because it requires a large number of nodes to be assessed to find the optimal path. As a result, although the Dijkstra algorithm can find the optimal path, it requires an excessive amount of computation, and thus, a route-finding algorithm that is more efficient than the Bellman Ford and Dijkstra algorithm is necessary. The A* algorithm was proposed by [PERSON] et al. in 1968 [PERSON] et al. (1968). This algorithm is based on the Dijkstra algorithm, but it increases the efficiency of the overall process by applying a new cost assessment methodology called a \"heuristic.\" A* has become the widely used routing algorithm because of its simplicity as well as its flexibility enabling utilization in various areas. In particular, the A* algorithm is specialized in single source-single destination, so that it has a high advantage in terms of computational efficiency in the case of ship operations where the departure and destination are clearly defined compared to the Bellman Ford algorithm specialized in single source-all pairs. The A* algorithm determines a path from the given start node to the given target node that has the smallest cost, such as least distance traveled and shortest time, as given in Equation (1). \[ \begin{array}{cc}\text{\emph{Minimize}}&f(n)=g(n)+h(n)\end{array}  \tag{1}\]  
where \(g(n)\) is the actual path cost from the start node \(s\in\mathbf{N}\) to the current node \(n\in\mathbf{N}\), and \(h(n)\) is the heuristic, which is the expected cost of traveling from current node \(n\in\mathbf{N}\) to the target node \(t\in\mathbf{N}\). In ordinary shortest-path problems, the \(L^{p}\)-norms, such as the Manhattan distance (\(L_{1}\)) and Euclidean distance (\(L_{2}\)), are widely used as heuristic functions. The main loop of the A* algorithm iteratively determines which of its paths to extend from the start node to the target node. The heuristic function has the largest value at the start node because the actual path cost is zero. As the current node gets close to the target node \(t\), the heuristic function value decreases and finally becomes zero for the target node. If the heuristic has a constant value of 0 regardless of the position of the node, the A* algorithm is equivalent to the Dijkstra algorithm. The Dijkstra algorithm searches all directions around the current node, whereas the A* algorithm continues to re-evaluate \(g(n)\) and \(h(n)\) values during the path exploration process, looking for a path with the minimum path cost to the target. The A* algorithm only searches in the direction toward the target, which is more efficient than the Dijkstra algorithm. If \(h(n)\) is never larger than the actual lowest cost from \(n\) to the goal, \(h(n)\) is considered admissible. If the heuristic function satisfies the admissibility condition, then A*, which minimizes \(f(n)\), is guaranteed to find an optimal solution from start to target. Conversely, if A* is admissible, i.e., there is an optimal path from start to target, the heuristic function is admissible, and A* terminates by finding the optimal path. If the heuristic \(h\) satisfies the triangular inequality, such as \(h(x)\leq d(x,y)+h(y)\) for every edge \((x,y)\) of the graph, \(h\) is considered monotonic or consistent. When the heuristic is consistent, A* using graph-search is guaranteed to find an optimal path. Additionally, A* is optimally efficient because there is no other algorithm that is guaranteed to expand fewer nodes than A*. If any path-finding algorithm expands fewer nodes than A*, the obtained optimal path may not be the real optimal one [21].