Consider algorithms to find shortest paths in a graph. The grassfire algorithm has a complexity of O(|V|) where V is the number of nodes or vertices. The Dijkstra's algorithm has a complexity of O((|V| + |E|) * log(|V|)) where E is the number of edges. Compared to A star, the Dijkstra's does not rely on properties of any heuristic which makes them popular. But I am trying to understand the advantage of Dijkstra's over Grassfire. Are there practical reasons why this is the case? Or am I simply seeing more cases of Dijkstra's compared to Grassfire due to the application areas such as navigation that I am working on?
$\begingroup$
$\endgroup$
0
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
In grassfire the distances are constant. All of your neighbors have equal length. In a weighted graph, grassfire will fail.
Graphfire is actually based on a small modification of BFS.
The Dijsktra works on weighted graphs, too.
Note: If all costs are equal, Dijkstra = BFS
Know the difference, and use them according to your need.
$\begingroup$
$\endgroup$
The Grassfire algorithm only works on a particular kind of graph; Dijkstra's algorithm works on any graph.
