# Near-Optimal Weather Routing by Using Improved A* Algorithm
## 2 Routing Algorithms
### Dijkstra Algorithm  
The Dijkstra algorithm is similar to the Bellman-Ford algorithm in that it explores an optimal path by performing edge relaxation; the only difference between the two is that the latter can handle negative weights, whereas the former cannot [15]. Unlike the Bellman-Ford algorithm, the Dijkstra algorithm selects the unvisited node with the lowest distance and calculates the distance from it to each unvisited neighbor; then, it updates the distance of the neighbor if it is smaller. This algorithm improves the efficiency of finding the optimal path by reducing the number of candidate nodes to be explored using a queue (or heap), which is a tree-based data structure designed to accelerate the operation of finding the maximum and minimum values.  
The Dijkstra algorithm utilizes a queue to save path costs from the start node to neighbor nodes. It sequentially selects the optimal node with the lowest path cost at each step in a queue and attempts to find the overall optimal path in the given graph. Therefore, the method of selecting the optimal path from the entire graph in succession by selecting the nodes considered optimal at each step is called a \"greedy algorithm.\" The Dijkstra algorithm can be regarded as one of the greedy algorithms. Consequently, because this greedy property of the Dijkstra algorithm limits the number of nodes that need to be explored to find the optimal path, it presents a remarkable advantage in terms of time complexity when compared with the Bellman-Ford algorithm. As described in Section 2.1, although the Dijkstra algorithm is not applicable when a negative edge weight exists, this is not a critical drawback because the optimal path finding for ship routes does not include negative weights. Because the shipping time is related directly to the path cost, the shipping cost does not include negative weights. Additionally, because the Dijkstra algorithm is more efficient than the Bellman-Ford algorithm, it is better to use the Dijkstra algorithm for the purpose of this study.  
Similar to the Bellman-Ford algorithm, the Dijkstra algorithm initializes the path cost of the start node to zero, while the other nodes have infinite values. The starting node is first placed in _Queue_ as the key of the \(d\) value, and then the neighbor node \(u\) with minimum cost is selected as the priority queue (_Queue_) by calculating the path costs of the adjacent nodes from the starting node, and the path cost is updated. This process is repeated until the path reaches the target node.  
The overall processes of the Dijkstra algorithm are as follows.  
1. For all _nodes_\(\in\)\(N\) in graph \(\mathbf{G}\) provided, initialize with \(d(node)=\infty\).
2. For source \(s\), initialize \(d(s)=0\) and put \(s\) into _Queue_ as key with value of \(d\).
3. Extract minimum valued node \(u\) from _Queue_.
4. Execute edge relaxation at \(u\), putting newly visited nodes into _Queue_.
5. Repeat iii. and iv. until the path reaches the goal node \(t\).  
Here, _Queue_ is a priority queue of visited nodes, _Queue_\(\subseteq\)\(\mathbf{V}\), and \(\mathbf{S}\) is a set of assessed nodes, \(\mathbf{S}\subseteq\)\(\mathbf{V}\). Algorithm 2 shows the pseudocode of the [PERSON] algorithm.  
```
1:functionDI\(|\)KSTRA(\(\mathbf{G}(\mathbf{V},\mathbf{E})\), \(\mathbf{W},s\), \(t\))
2:for all\(u\in V-\{s\}\)do
3:\(d[v]\infty\), pred\([v]nil\)
4:\(d[s]0\)
5:Queue \(\leftarrow\)\(\{s\}\), \(\mathbf{S}\leftarrow\varnothing\)
6:whileQueue \(\
eq\)\(\varnothing\)do
7:\(u\_{charrated\_min}_{d}(\mathbf{Queue})\)
8:\(\mathbf{S}\overset{update}{\leftarrow}\mathbf{S}\cup\{u\}\)
9:if\(u=t\)then
10:return\(d\), MAKEPATH\((t,\,pred)\) : Tracking backward
11:for all\(e\in\{e_{u,p}\in\mathbf{E}\,\big{|}\,u\in\mathbf{V},\,v\in\textit{adjacent}[u]\}\)do : Edge relaxation
12:if\(d[v]>d[u]+\mathbf{W}(e)\)then
13:\(d[v]\overset{update}{\leftarrow}d[u]+\mathbf{W}(e)\)
14:\(pred[v]\overset{update}{\leftarrow}u\)
15:Queue \(\leftarrow\)Queue \(\cup\{u\}\)
16:return\(\varnothing\)
```  
**Algorithm 2** Dijkstra's Algorithm