# Near-Optimal Weather Routing by Using Improved A* Algorithm
## 2 Routing Algorithms  
### Bellman-Ford Algorithm  
The Bellman-Ford algorithm finds the shortest path between a single source node and all other nodes in a given graph of paths through nodes [12; 13; 14]. The Bellman-Ford algorithm estimates the lengths of the paths from the source node (start node) to all other nodes and then iteratively relaxes the edges between two vertices by finding new paths that are shorter than the previously estimated paths. For example, if \(s\) is a source (start) node and \(u\) and \(v\) are arbitrary nodes explored, as shown in Figure 1, the wave arrows \(d(s,u)\) and \(d(s,v)\) indicate the optimal path costs passing through multiple nodes between \(s\) and \(u\) or \(v\), respectively. The dashed arrow \(c(u,v)\) indicates the path cost (edge weight) of two neighbor nodes \(u\) and \(v\). When the edge linking \(u\) to \(v\) with path cost of \(c(u,v)\) is found, as shown in Figure 1, and if the inequality \(d(s,u)+c(u,v)<d(s,v)\) is satisfied, the path with a cost of \(d(s,v)\) is no longer the optimal path from \(s\) to \(v\). Thus, the path through \(u\) is included as a subset of the optimal solution path instead of the existing path with the cost of \(d(s,v)\). The optimal path between \(s\) and \(v\) is updated by the path via \(u\), which is called edge relaxation. If \(d(s,u)\) is properly relaxed, i.e., \(d(s,u)\) yields the suboptimal path of the optimal solution path, the triangular inequality \(d(s,u)+c(u,v)\geq d(s,v)\) is satisfied. This process is repeated until edge relaxation does not occur. The edge weights can be either negative or positive values according to the sign of the path cost. For example, one can pay the cost from one node to another node (positive weight), but one can obtain some advantage (negative weight) reversely. If the sum of the edges is a negative value, the graph contains a negative cycle. The negative cycle can lead to a routing process with an infinite loop in terms of an algorithm that tries to minimize path cost; thus, the Bellman-Ford algorithm returns an error when any negative cycles are detected. Let \(\mathbf{N}\) be the set of defined nodes, \(\mathbf{G}\) denote the finite graph consisting of nodes and edges, and \(d(node)\) denote the cost of the path connecting source \(s\) to _node_. The path cost between all nodes is initialized to infinity, and the path cost is reset to zero for the starting node, \(s\). The triangular inequality  
Figure 1: Principle of edge relaxation. condition shown in Figure 1 is used to find the optimal path that minimizes the path cost of passing through nodes in the graph \(\mathbf{G}\). If there is a negative cycle in \(\mathbf{G}\), the entire process is halted. The basic processes of the Bellman-Ford algorithm are as follows, and Algorithm 1 shows the pseudocode. 1. For all \(nodes\in\mathbf{N}\) in graph \(\mathbf{G}\) provided, initialize with \(d(node)=\infty\). 2. For source \(s\), initialize \(d(s)=0\). 3. Execute edge relaxation in accordance with triangular inequality. 4. Repeat iii. until there is no node left to update \(d\). 5. If there are any negative cycles in \(\mathbf{G}\), stop the process, even if the condition iv. is unfulfilled.