# Search and Rescue in a Maze-like Environment with Ant and Dijkstra Algorithms
## 2 Background
### Nature-Inspired Approaches to Finding the Shortest Path
#### 2.3.2 The Dijkstra Algorithm  
[PERSON]'s algorithm is a well-known search algorithm developed by a Dutch computer scientist, [PERSON], in 1959 [92], which can be applied on a graph. The algorithm is one of the solutions on Single-Source Shortest Path problem (SSSP) with directed or undirected graphs, and has edges with non-negative weights [93]. The SSSP is defined as finding the shortest path from a distinguished vertex in a graph called source to every other vertex in the graph. [PERSON]'s algorithm follows the greedy approach, which means it finds an optimal path with the least total cost (shortest path from source to destination) [94].  
The algorithm begins with a graph with nodes, \(u\) or \(v\), weighted edges connecting nodes denoted as \((u,v)\) and weights denoted as _CostMatrix(\(u\),\(v\))_. The initiation of values and related steps before starting the path finding are:  
* An array holding all edges costs (_distance(\(i\))_) where all values are initiated to infinity except the first value (_distance(source)_), which is set to zero.
* An array that contains all the nodes that have been visited during the search, which, by the end, contains all nodes in the graph (denoted as _visited_). Then, the algorithm proceeds as follows:
* While the visited array does not contain all nodes, we take node \(v\) with the least _distance(\(v\))_. Initially, it will be the source because _distance(source)_ is set to zero.
* Node \(v\) is then added to the visited array, indicating that it has been visited.
* Update distance values of adjacent nodes (\(u\)) to the node \(v\).
* If \[\textit{distance(}v\text{)}+\textit{CostMatrix(}u\text{,}v\text{)}<\textit{ distance(}u\text{)},\] then there is a new minimal distance founded for \(u\), so _distance(\(u\))_ is updated with the new minimal value. Otherwise, no changes are made to _distance(\(u\))_. Finally, after the algorithm has visited all nodes in the graph and the smallest distance to each node is found, distance will now contain the shortest path tree from the source node [95].  
Dijkstra's main advantage is that it finds the most optimal path in an efficient manner. However, it may incur a large cost in computational time due to the blind search it performs to calculate the optimal path. Another weakness is that the algorithm does not consider negative edges. However, in this project, the distance is seen as the cost with positive value, which means that only positive edges are considered, following [92]. A brief summary of examples in the literature on using Dijkstra is shown in Table 2.  
\begin{table}
\begin{tabular}{c c c c} \hline \hline
**Ref** & **LP** & **HT** & **Algorithm Used** \\ \hline
[78] & & ✓ & Improved ACO \\
[79] & ✓ & & Artificial Potential Field Method \\
[80] & ✓ & ✓ & Multi Pheromones for tracking targets \\
[81] & ✓ & ✓ & Improved ACO Heuristic Function \\
[82] & & ✓ & Simple ACO \\
[83] & ✓ & ✓ & Repellent Pheromone for coverage \\
[84] & ✓ & ✓ & Advanced PSO \\
[85] & & ✓ & Genetic Algorithm with ACO \\
[86] & & ✓ & Hybrid ACO w. Random- + RL based-Search \\
[87] & ✓ & & Point Bug Algorithm \\
[88] & ✓ & & Dijkstra Algorithm \\
[89] & ✓ & ✓ & Fuzzy Logic with Counter ACO \\
[90] & & ✓ & PSO in partially known environments \\
[91] & ✓ & ✓ & Combination of multiple pheromones \\ \hline \hline \end{tabular}
\end{table}
Table 1: Research in the field of deterministic and heuristic path planning strategies in maze-like environments, including Ant Colony Optimization (ACO), Particle Swarm optimization (PSO), and others. **LP** stands for _Local Planning_, **HT** stands for _Heuristic Technique_.