![](https://csdnimg.cn/release/download_crawler_static/86622370/bg5.jpg)
Vehicles 2021, 3 452
single-source (finding shortest paths from a source vertex to all other vertices present in
the graph) shortest path in a positive weighted graph [19].
Dijkstra is a reliable algorithm for path planning. It is also memory heavy [
20
] as it has
to compute all the possible outcomes in order to determine the shortest path, and it cannot
handle negative edges. Its computation complexity is O(n2) with n being the number of
nodes in the network [21]. Due to its limitations, many improved variants arose based on
the applications. As we discussed earlier for a memory drawback, a new memory scheme
was introduced [18], there was also a solution to map with a huge cost factor [16].
We can generalize that the Dijkstra algorithm is best suited for a static environment
and/or global path planning as most of the data required are pre-defined for computation
of shortest path; however, there are applications where the Dijkstra algorithm has been used
for dynamic environments. In this case, the environment is partially known or completely
unknown, and thus the node information with respect to obstacles is computed on the fly;
this is called local planning, and the Dijkstra algorithm is run for evaluation of the shortest
path computation. Please see classification Table 1 for Dijkstra and its variants. However,
we cannot use the Dijkstra algorithm alone within dynamic environments [22]
Table 1.
Suitability of the Dijkstra algorithm and its variants as classified based upon static and
dynamic environmental constraints.
Algorithm Static Constraints Dynamic Constraints
Dijkstra x
Improved Dijkstra x
Multi-layer dictionary x x
Floyd and Dijkstra x
2.2. A* Algorithm
The A* Algorithm is a popular graph traversal path planning algorithm. A* operates
similarly to Dijkstra’s algorithm except that it guides its search towards the most promising
states, potentially saving a significant amount of computation time [
23
]. A* is the most
widely used for approaching a near optimal solution [
24
] with the available data-set/node.
It is widely used in static environments; there are instances where this algorithm
is used in dynamic environments [
25
]. The base function can be tailored to a specific
application or environment based on our needs. A* is similar to Dijkstra in that it works
based on the lowest cost path tree from the initial point to the final target point. The base
algorithm uses the least expensive path and expands it using the function shown below
f (n) = g(n) + h(n) (1)
where
g(n)
is the actual cost from node n to the initial node, and
h(n)
is the cost of the
optimal path from the target node to n.
The A* algorithm is widely used in the gaming industry [
26
], and with the develop-
ment of artificial intelligence, the A* algorithm has since been improved and tailored for
applications, including robot path planning, urban intelligent transportation, graph theory,
and automatic control [27–31].
It is simpler and less computationally-heavy than many other path planning algo-
rithms, with its efficiency lending itself to operation on constrained and embedded sys-
tems [
32
,
33
]. The A* algorithm is a heuristic algorithm that uses heuristic information to
find the optimal path. The A* algorithm needs to search for nodes in the map and set
appropriate heuristic functions for guidance, such as the Euclidean distance, Manhattan
distance, or Diagonal distance [
34
,
35
]. An algorithm is governed by two factors for effi-
ciency resources used for performance of the task and response time or computation time
taken for performance of the task.
There is a trade off between speed and accuracy when the A* algorithm is used. We
can decrease the time complexity of the algorithm in exchange for greater memory, or