1
$\begingroup$

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?

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

The Grassfire algorithm only works on a particular kind of graph; Dijkstra's algorithm works on any graph.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.