ROS Answers: Open Source Q&A Forum - RSS feedhttps://answers.ros.org/questions/Open source question and answer forum written in Python and DjangoenROS Answers is licensed under Creative Commons Attribution 3.0Thu, 10 Oct 2019 05:17:20 -0500Why navfn is using Dijkstra?https://answers.ros.org/question/28366/why-navfn-is-using-dijkstra/As an algorithm learner, I'm just curious about why `navfn` was is first equipped with `dijkstra` search algorith. [The answer at this question](http://answers.ros.org/question/11388/navfn-algorism?answer=16891#answer-container-16891) explains how `navfn` works using `dijkstra`, but what is the reason it was selected instead of other algorithms that are equally good (e.g. `A*`) ?Thu, 23 Feb 2012 16:18:59 -0600https://answers.ros.org/question/28366/why-navfn-is-using-dijkstra/Answer by bhaskara for <p>As an algorithm learner, I'm just curious about why <code>navfn</code> was is first equipped with <code>dijkstra</code> search algorith. <a href="http://answers.ros.org/question/11388/navfn-algorism?answer=16891#answer-container-16891">The answer at this question</a> explains how <code>navfn</code> works using <code>dijkstra</code>, but what is the reason it was selected instead of other algorithms that are equally good (e.g. <code>A*</code>) ?</p>
https://answers.ros.org/question/28366/why-navfn-is-using-dijkstra/?answer=34926#post-id-34926If you look at the navfn code, you'll see that there is in fact an optimized A* algorithm in there. It was not used because there was a bug and nobody had the cycles to fix it. IMO there's a lot of premature optimization here, given that global planning does not need to be happening that often. The right thing to do is to use a principled and efficient A* implementation such as sbpl :)Sat, 26 May 2012 09:08:37 -0500https://answers.ros.org/question/28366/why-navfn-is-using-dijkstra/?answer=34926#post-id-34926Comment by navidzarrabi for <p>If you look at the navfn code, you'll see that there is in fact an optimized A* algorithm in there. It was not used because there was a bug and nobody had the cycles to fix it. IMO there's a lot of premature optimization here, given that global planning does not need to be happening that often. The right thing to do is to use a principled and efficient A* implementation such as sbpl :)</p>
https://answers.ros.org/question/28366/why-navfn-is-using-dijkstra/?comment=335067#post-id-335067Are you sure it is using an Optimized A* ?
ROS wiki says "support for an A* heuristic may also be added in the near future". You mean they have already added A* support but never edited their description in ROS wiki?Thu, 10 Oct 2019 05:17:20 -0500https://answers.ros.org/question/28366/why-navfn-is-using-dijkstra/?comment=335067#post-id-335067Comment by 2ROS0 for <p>If you look at the navfn code, you'll see that there is in fact an optimized A* algorithm in there. It was not used because there was a bug and nobody had the cycles to fix it. IMO there's a lot of premature optimization here, given that global planning does not need to be happening that often. The right thing to do is to use a principled and efficient A* implementation such as sbpl :)</p>
https://answers.ros.org/question/28366/why-navfn-is-using-dijkstra/?comment=197315#post-id-197315what do you mean by nobody had the "cycles to fix it" ?Wed, 12 Nov 2014 17:54:27 -0600https://answers.ros.org/question/28366/why-navfn-is-using-dijkstra/?comment=197315#post-id-197315Comment by 130s for <p>If you look at the navfn code, you'll see that there is in fact an optimized A* algorithm in there. It was not used because there was a bug and nobody had the cycles to fix it. IMO there's a lot of premature optimization here, given that global planning does not need to be happening that often. The right thing to do is to use a principled and efficient A* implementation such as sbpl :)</p>
https://answers.ros.org/question/28366/why-navfn-is-using-dijkstra/?comment=34929#post-id-34929While Dimitri's answer initiated a meaningful discussion, I thought I have to choose this response as a more direct answer to my particular question.Sat, 26 May 2012 09:23:01 -0500https://answers.ros.org/question/28366/why-navfn-is-using-dijkstra/?comment=34929#post-id-34929Comment by Void for <p>If you look at the navfn code, you'll see that there is in fact an optimized A* algorithm in there. It was not used because there was a bug and nobody had the cycles to fix it. IMO there's a lot of premature optimization here, given that global planning does not need to be happening that often. The right thing to do is to use a principled and efficient A* implementation such as sbpl :)</p>
https://answers.ros.org/question/28366/why-navfn-is-using-dijkstra/?comment=308786#post-id-308786I believe it's talking about free timeFri, 16 Nov 2018 13:55:01 -0600https://answers.ros.org/question/28366/why-navfn-is-using-dijkstra/?comment=308786#post-id-308786Answer by DimitriProsser for <p>As an algorithm learner, I'm just curious about why <code>navfn</code> was is first equipped with <code>dijkstra</code> search algorith. <a href="http://answers.ros.org/question/11388/navfn-algorism?answer=16891#answer-container-16891">The answer at this question</a> explains how <code>navfn</code> works using <code>dijkstra</code>, but what is the reason it was selected instead of other algorithms that are equally good (e.g. <code>A*</code>) ?</p>
https://answers.ros.org/question/28366/why-navfn-is-using-dijkstra/?answer=28399#post-id-28399Here is my opinion: The choice of Dijkstra's algorithm was largely due to the ability to more accurately produce the shortest path to a goal. Navfn's algorithm provides a high degree of accuracy because of the number of points that it considers during planning.
I have to disagree with @Ben, however. A* is typically noted as having a better performance than Dijkstra's, primarily because of its ability to use heuristics, but also purely based on the nature of the algorithm. A* is a greedy, best-first search algorithm, so it uses heuristics to only expand points it believes to be the most likely to provide the shortest route.
The performance advantage of A*, however, can result in less-optimal paths, whereas Dijkstra's is more likely to produce an optimal path to the goal.
A great way to understand these two algorithms is to look at the wikipedia pages for [A*](http://en.wikipedia.org/wiki/A*_search_algorithm) and [Dijkstra's](http://en.wikipedia.org/wiki/Dijkstra's_algorithm) and simply look at the animated graphics of the algorithm. You'll be able to see the difference quite clearly.
**EDIT**:
"The Manhattan distance heuristic generates optimal paths in real time. However, this is true only in the case where there are no or very few static obstacles. As the size and the number of obstacles increases, A* not only spends more time on searching but also requires more memory for the nodes as it needs more nodes to find a path."
Source: [this](http://wlv.openrepository.com/wlv/bitstream/2436/31520/1/CGAIDE%25202004_Kumar%2520et%2520al.pdf) paperFri, 24 Feb 2012 02:58:35 -0600https://answers.ros.org/question/28366/why-navfn-is-using-dijkstra/?answer=28399#post-id-28399Comment by dornhege for <p>Here is my opinion: The choice of Dijkstra's algorithm was largely due to the ability to more accurately produce the shortest path to a goal. Navfn's algorithm provides a high degree of accuracy because of the number of points that it considers during planning. </p>
<p>I have to disagree with <a href="/users/33/ben/">@ben</a>, however. A* is typically noted as having a better performance than Dijkstra's, primarily because of its ability to use heuristics, but also purely based on the nature of the algorithm. A* is a greedy, best-first search algorithm, so it uses heuristics to only expand points it believes to be the most likely to provide the shortest route. </p>
<p>The performance advantage of A*, however, can result in less-optimal paths, whereas Dijkstra's is more likely to produce an optimal path to the goal. </p>
<p>A great way to understand these two algorithms is to look at the wikipedia pages for <a href="http://en.wikipedia.org/wiki/A*_search_algorithm">A*</a> and <a href="http://en.wikipedia.org/wiki/Dijkstra's_algorithm">Dijkstra's</a> and simply look at the animated graphics of the algorithm. You'll be able to see the difference quite clearly. </p>
<p><strong>EDIT</strong>:</p>
<p>"The Manhattan distance heuristic generates optimal paths in real time. However, this is true only in the case where there are no or very few static obstacles. As the size and the number of obstacles increases, A* not only spends more time on searching but also requires more memory for the nodes as it needs more nodes to find a path."</p>
<p>Source: <a href="http://wlv.openrepository.com/wlv/bitstream/2436/31520/1/CGAIDE%25202004_Kumar%2520et%2520al.pdf">this</a> paper</p>
https://answers.ros.org/question/28366/why-navfn-is-using-dijkstra/?comment=35137#post-id-35137A* only outperforms Dijkstra in #expansions. Runtime might be worse depending on the computation time of the heuristic. Nevertheless, one could always use constant zero as a heuristic for A* to get dijkstra.Tue, 29 May 2012 00:41:07 -0500https://answers.ros.org/question/28366/why-navfn-is-using-dijkstra/?comment=35137#post-id-35137Comment by Ivan Dryanovski for <p>Here is my opinion: The choice of Dijkstra's algorithm was largely due to the ability to more accurately produce the shortest path to a goal. Navfn's algorithm provides a high degree of accuracy because of the number of points that it considers during planning. </p>
<p>I have to disagree with <a href="/users/33/ben/">@ben</a>, however. A* is typically noted as having a better performance than Dijkstra's, primarily because of its ability to use heuristics, but also purely based on the nature of the algorithm. A* is a greedy, best-first search algorithm, so it uses heuristics to only expand points it believes to be the most likely to provide the shortest route. </p>
<p>The performance advantage of A*, however, can result in less-optimal paths, whereas Dijkstra's is more likely to produce an optimal path to the goal. </p>
<p>A great way to understand these two algorithms is to look at the wikipedia pages for <a href="http://en.wikipedia.org/wiki/A*_search_algorithm">A*</a> and <a href="http://en.wikipedia.org/wiki/Dijkstra's_algorithm">Dijkstra's</a> and simply look at the animated graphics of the algorithm. You'll be able to see the difference quite clearly. </p>
<p><strong>EDIT</strong>:</p>
<p>"The Manhattan distance heuristic generates optimal paths in real time. However, this is true only in the case where there are no or very few static obstacles. As the size and the number of obstacles increases, A* not only spends more time on searching but also requires more memory for the nodes as it needs more nodes to find a path."</p>
<p>Source: <a href="http://wlv.openrepository.com/wlv/bitstream/2436/31520/1/CGAIDE%25202004_Kumar%2520et%2520al.pdf">this</a> paper</p>
https://answers.ros.org/question/28366/why-navfn-is-using-dijkstra/?comment=28431#post-id-28431@dornhege My hunch is the same: it uses Dijkstra because it was easier to implement, but A* would perform just as good, and likely better.Fri, 24 Feb 2012 05:50:14 -0600https://answers.ros.org/question/28366/why-navfn-is-using-dijkstra/?comment=28431#post-id-28431Comment by dornhege for <p>Here is my opinion: The choice of Dijkstra's algorithm was largely due to the ability to more accurately produce the shortest path to a goal. Navfn's algorithm provides a high degree of accuracy because of the number of points that it considers during planning. </p>
<p>I have to disagree with <a href="/users/33/ben/">@ben</a>, however. A* is typically noted as having a better performance than Dijkstra's, primarily because of its ability to use heuristics, but also purely based on the nature of the algorithm. A* is a greedy, best-first search algorithm, so it uses heuristics to only expand points it believes to be the most likely to provide the shortest route. </p>
<p>The performance advantage of A*, however, can result in less-optimal paths, whereas Dijkstra's is more likely to produce an optimal path to the goal. </p>
<p>A great way to understand these two algorithms is to look at the wikipedia pages for <a href="http://en.wikipedia.org/wiki/A*_search_algorithm">A*</a> and <a href="http://en.wikipedia.org/wiki/Dijkstra's_algorithm">Dijkstra's</a> and simply look at the animated graphics of the algorithm. You'll be able to see the difference quite clearly. </p>
<p><strong>EDIT</strong>:</p>
<p>"The Manhattan distance heuristic generates optimal paths in real time. However, this is true only in the case where there are no or very few static obstacles. As the size and the number of obstacles increases, A* not only spends more time on searching but also requires more memory for the nodes as it needs more nodes to find a path."</p>
<p>Source: <a href="http://wlv.openrepository.com/wlv/bitstream/2436/31520/1/CGAIDE%25202004_Kumar%2520et%2520al.pdf">this</a> paper</p>
https://answers.ros.org/question/28366/why-navfn-is-using-dijkstra/?comment=28425#post-id-28425With risk of sounding super-pedantic: A* is guaranteed to be optimal as A* requires an admissible heuristik (otherwise it's not A*). Manhattan and Euclidian are admissible on gridmaps.Fri, 24 Feb 2012 05:28:01 -0600https://answers.ros.org/question/28366/why-navfn-is-using-dijkstra/?comment=28425#post-id-28425Comment by Dan Lazewatsky for <p>Here is my opinion: The choice of Dijkstra's algorithm was largely due to the ability to more accurately produce the shortest path to a goal. Navfn's algorithm provides a high degree of accuracy because of the number of points that it considers during planning. </p>
<p>I have to disagree with <a href="/users/33/ben/">@ben</a>, however. A* is typically noted as having a better performance than Dijkstra's, primarily because of its ability to use heuristics, but also purely based on the nature of the algorithm. A* is a greedy, best-first search algorithm, so it uses heuristics to only expand points it believes to be the most likely to provide the shortest route. </p>
<p>The performance advantage of A*, however, can result in less-optimal paths, whereas Dijkstra's is more likely to produce an optimal path to the goal. </p>
<p>A great way to understand these two algorithms is to look at the wikipedia pages for <a href="http://en.wikipedia.org/wiki/A*_search_algorithm">A*</a> and <a href="http://en.wikipedia.org/wiki/Dijkstra's_algorithm">Dijkstra's</a> and simply look at the animated graphics of the algorithm. You'll be able to see the difference quite clearly. </p>
<p><strong>EDIT</strong>:</p>
<p>"The Manhattan distance heuristic generates optimal paths in real time. However, this is true only in the case where there are no or very few static obstacles. As the size and the number of obstacles increases, A* not only spends more time on searching but also requires more memory for the nodes as it needs more nodes to find a path."</p>
<p>Source: <a href="http://wlv.openrepository.com/wlv/bitstream/2436/31520/1/CGAIDE%25202004_Kumar%2520et%2520al.pdf">this</a> paper</p>
https://answers.ros.org/question/28366/why-navfn-is-using-dijkstra/?comment=28414#post-id-28414When planning 2D paths for a robot, when would euclidian or manhattan distance heuristics not be admissible? I can't imagine a situation when the straight-lilne distance would be an overestimate.Fri, 24 Feb 2012 04:32:19 -0600https://answers.ros.org/question/28366/why-navfn-is-using-dijkstra/?comment=28414#post-id-28414Comment by mkoval for <p>Here is my opinion: The choice of Dijkstra's algorithm was largely due to the ability to more accurately produce the shortest path to a goal. Navfn's algorithm provides a high degree of accuracy because of the number of points that it considers during planning. </p>
<p>I have to disagree with <a href="/users/33/ben/">@ben</a>, however. A* is typically noted as having a better performance than Dijkstra's, primarily because of its ability to use heuristics, but also purely based on the nature of the algorithm. A* is a greedy, best-first search algorithm, so it uses heuristics to only expand points it believes to be the most likely to provide the shortest route. </p>
<p>The performance advantage of A*, however, can result in less-optimal paths, whereas Dijkstra's is more likely to produce an optimal path to the goal. </p>
<p>A great way to understand these two algorithms is to look at the wikipedia pages for <a href="http://en.wikipedia.org/wiki/A*_search_algorithm">A*</a> and <a href="http://en.wikipedia.org/wiki/Dijkstra's_algorithm">Dijkstra's</a> and simply look at the animated graphics of the algorithm. You'll be able to see the difference quite clearly. </p>
<p><strong>EDIT</strong>:</p>
<p>"The Manhattan distance heuristic generates optimal paths in real time. However, this is true only in the case where there are no or very few static obstacles. As the size and the number of obstacles increases, A* not only spends more time on searching but also requires more memory for the nodes as it needs more nodes to find a path."</p>
<p>Source: <a href="http://wlv.openrepository.com/wlv/bitstream/2436/31520/1/CGAIDE%25202004_Kumar%2520et%2520al.pdf">this</a> paper</p>
https://answers.ros.org/question/28366/why-navfn-is-using-dijkstra/?comment=34909#post-id-34909@DimitriProsser: The paper you linked to does **not** claim that Dijkstra's outperforms A\*. Instead, it says that A* (and, thus, Dijkstra's) may perform too slowly to use in a game. @IsaacSaito: Since A* will always outperform Dijkstra's, why not remove Dijkstra's from navfn entirely?Sat, 26 May 2012 04:45:49 -0500https://answers.ros.org/question/28366/why-navfn-is-using-dijkstra/?comment=34909#post-id-34909Comment by dornhege for <p>Here is my opinion: The choice of Dijkstra's algorithm was largely due to the ability to more accurately produce the shortest path to a goal. Navfn's algorithm provides a high degree of accuracy because of the number of points that it considers during planning. </p>
<p>I have to disagree with <a href="/users/33/ben/">@ben</a>, however. A* is typically noted as having a better performance than Dijkstra's, primarily because of its ability to use heuristics, but also purely based on the nature of the algorithm. A* is a greedy, best-first search algorithm, so it uses heuristics to only expand points it believes to be the most likely to provide the shortest route. </p>
<p>The performance advantage of A*, however, can result in less-optimal paths, whereas Dijkstra's is more likely to produce an optimal path to the goal. </p>
<p>A great way to understand these two algorithms is to look at the wikipedia pages for <a href="http://en.wikipedia.org/wiki/A*_search_algorithm">A*</a> and <a href="http://en.wikipedia.org/wiki/Dijkstra's_algorithm">Dijkstra's</a> and simply look at the animated graphics of the algorithm. You'll be able to see the difference quite clearly. </p>
<p><strong>EDIT</strong>:</p>
<p>"The Manhattan distance heuristic generates optimal paths in real time. However, this is true only in the case where there are no or very few static obstacles. As the size and the number of obstacles increases, A* not only spends more time on searching but also requires more memory for the nodes as it needs more nodes to find a path."</p>
<p>Source: <a href="http://wlv.openrepository.com/wlv/bitstream/2436/31520/1/CGAIDE%25202004_Kumar%2520et%2520al.pdf">this</a> paper</p>
https://answers.ros.org/question/28366/why-navfn-is-using-dijkstra/?comment=28426#post-id-28426A* also guarantees minimal number of nodes expanded, so the only reason to be less performant than Dijkstra's would be if the heuristic computation is slowing it down. Maybe the answer to the question is just: Because it was easier to implement and doesn't require heuristics?Fri, 24 Feb 2012 05:29:23 -0600https://answers.ros.org/question/28366/why-navfn-is-using-dijkstra/?comment=28426#post-id-28426Comment by Ivan Dryanovski for <p>Here is my opinion: The choice of Dijkstra's algorithm was largely due to the ability to more accurately produce the shortest path to a goal. Navfn's algorithm provides a high degree of accuracy because of the number of points that it considers during planning. </p>
<p>I have to disagree with <a href="/users/33/ben/">@ben</a>, however. A* is typically noted as having a better performance than Dijkstra's, primarily because of its ability to use heuristics, but also purely based on the nature of the algorithm. A* is a greedy, best-first search algorithm, so it uses heuristics to only expand points it believes to be the most likely to provide the shortest route. </p>
<p>The performance advantage of A*, however, can result in less-optimal paths, whereas Dijkstra's is more likely to produce an optimal path to the goal. </p>
<p>A great way to understand these two algorithms is to look at the wikipedia pages for <a href="http://en.wikipedia.org/wiki/A*_search_algorithm">A*</a> and <a href="http://en.wikipedia.org/wiki/Dijkstra's_algorithm">Dijkstra's</a> and simply look at the animated graphics of the algorithm. You'll be able to see the difference quite clearly. </p>
<p><strong>EDIT</strong>:</p>
<p>"The Manhattan distance heuristic generates optimal paths in real time. However, this is true only in the case where there are no or very few static obstacles. As the size and the number of obstacles increases, A* not only spends more time on searching but also requires more memory for the nodes as it needs more nodes to find a path."</p>
<p>Source: <a href="http://wlv.openrepository.com/wlv/bitstream/2436/31520/1/CGAIDE%25202004_Kumar%2520et%2520al.pdf">this</a> paper</p>
https://answers.ros.org/question/28366/why-navfn-is-using-dijkstra/?comment=28402#post-id-28402With the risk of sounding pedanitc, isn't A* guaranteed to be optimal when the heuristic does not overestimate the distance to the goal? Euclidean or Manhattan distances should produce optimal paths with A*, on grid maps.Fri, 24 Feb 2012 03:10:25 -0600https://answers.ros.org/question/28366/why-navfn-is-using-dijkstra/?comment=28402#post-id-28402Comment by mkoval for <p>Here is my opinion: The choice of Dijkstra's algorithm was largely due to the ability to more accurately produce the shortest path to a goal. Navfn's algorithm provides a high degree of accuracy because of the number of points that it considers during planning. </p>
<p>I have to disagree with <a href="/users/33/ben/">@ben</a>, however. A* is typically noted as having a better performance than Dijkstra's, primarily because of its ability to use heuristics, but also purely based on the nature of the algorithm. A* is a greedy, best-first search algorithm, so it uses heuristics to only expand points it believes to be the most likely to provide the shortest route. </p>
<p>The performance advantage of A*, however, can result in less-optimal paths, whereas Dijkstra's is more likely to produce an optimal path to the goal. </p>
<p>A great way to understand these two algorithms is to look at the wikipedia pages for <a href="http://en.wikipedia.org/wiki/A*_search_algorithm">A*</a> and <a href="http://en.wikipedia.org/wiki/Dijkstra's_algorithm">Dijkstra's</a> and simply look at the animated graphics of the algorithm. You'll be able to see the difference quite clearly. </p>
<p><strong>EDIT</strong>:</p>
<p>"The Manhattan distance heuristic generates optimal paths in real time. However, this is true only in the case where there are no or very few static obstacles. As the size and the number of obstacles increases, A* not only spends more time on searching but also requires more memory for the nodes as it needs more nodes to find a path."</p>
<p>Source: <a href="http://wlv.openrepository.com/wlv/bitstream/2436/31520/1/CGAIDE%25202004_Kumar%2520et%2520al.pdf">this</a> paper</p>
https://answers.ros.org/question/28366/why-navfn-is-using-dijkstra/?comment=35328#post-id-35328@domhenge: Exactly: It seems strange to duplicate all of the search code just to change the heuristic from zero to an L1 or L2 norm. Also, you make a good point about the overhead in computing the heuristic. I hadn't considered that.Thu, 31 May 2012 03:29:37 -0500https://answers.ros.org/question/28366/why-navfn-is-using-dijkstra/?comment=35328#post-id-35328Comment by 130s for <p>Here is my opinion: The choice of Dijkstra's algorithm was largely due to the ability to more accurately produce the shortest path to a goal. Navfn's algorithm provides a high degree of accuracy because of the number of points that it considers during planning. </p>
<p>I have to disagree with <a href="/users/33/ben/">@ben</a>, however. A* is typically noted as having a better performance than Dijkstra's, primarily because of its ability to use heuristics, but also purely based on the nature of the algorithm. A* is a greedy, best-first search algorithm, so it uses heuristics to only expand points it believes to be the most likely to provide the shortest route. </p>
<p>The performance advantage of A*, however, can result in less-optimal paths, whereas Dijkstra's is more likely to produce an optimal path to the goal. </p>
<p>A great way to understand these two algorithms is to look at the wikipedia pages for <a href="http://en.wikipedia.org/wiki/A*_search_algorithm">A*</a> and <a href="http://en.wikipedia.org/wiki/Dijkstra's_algorithm">Dijkstra's</a> and simply look at the animated graphics of the algorithm. You'll be able to see the difference quite clearly. </p>
<p><strong>EDIT</strong>:</p>
<p>"The Manhattan distance heuristic generates optimal paths in real time. However, this is true only in the case where there are no or very few static obstacles. As the size and the number of obstacles increases, A* not only spends more time on searching but also requires more memory for the nodes as it needs more nodes to find a path."</p>
<p>Source: <a href="http://wlv.openrepository.com/wlv/bitstream/2436/31520/1/CGAIDE%25202004_Kumar%2520et%2520al.pdf">this</a> paper</p>
https://answers.ros.org/question/28366/why-navfn-is-using-dijkstra/?comment=29698#post-id-29698Thanks. Btw it seems to me that A* is also implemented and not just in use (navfn::NavFn Class). It's just `NavfnROS::computePotential` calls the one that's associated with Dijkstra (navfn_ros.cpp), although I've not found if A* function is tested. I opened a ticket http://goo.gl/0pJzdWed, 14 Mar 2012 05:31:49 -0500https://answers.ros.org/question/28366/why-navfn-is-using-dijkstra/?comment=29698#post-id-29698Comment by DimitriProsser for <p>Here is my opinion: The choice of Dijkstra's algorithm was largely due to the ability to more accurately produce the shortest path to a goal. Navfn's algorithm provides a high degree of accuracy because of the number of points that it considers during planning. </p>
<p>I have to disagree with <a href="/users/33/ben/">@ben</a>, however. A* is typically noted as having a better performance than Dijkstra's, primarily because of its ability to use heuristics, but also purely based on the nature of the algorithm. A* is a greedy, best-first search algorithm, so it uses heuristics to only expand points it believes to be the most likely to provide the shortest route. </p>
<p>The performance advantage of A*, however, can result in less-optimal paths, whereas Dijkstra's is more likely to produce an optimal path to the goal. </p>
<p>A great way to understand these two algorithms is to look at the wikipedia pages for <a href="http://en.wikipedia.org/wiki/A*_search_algorithm">A*</a> and <a href="http://en.wikipedia.org/wiki/Dijkstra's_algorithm">Dijkstra's</a> and simply look at the animated graphics of the algorithm. You'll be able to see the difference quite clearly. </p>
<p><strong>EDIT</strong>:</p>
<p>"The Manhattan distance heuristic generates optimal paths in real time. However, this is true only in the case where there are no or very few static obstacles. As the size and the number of obstacles increases, A* not only spends more time on searching but also requires more memory for the nodes as it needs more nodes to find a path."</p>
<p>Source: <a href="http://wlv.openrepository.com/wlv/bitstream/2436/31520/1/CGAIDE%25202004_Kumar%2520et%2520al.pdf">this</a> paper</p>
https://answers.ros.org/question/28366/why-navfn-is-using-dijkstra/?comment=28403#post-id-28403A* can certainly produce optimal paths with the correct heuristic. Speaking general terms, however, it's more likely that A* will be sub-optimal than Dijkstra's (if you consider a wide variety of situations). Fri, 24 Feb 2012 03:17:43 -0600https://answers.ros.org/question/28366/why-navfn-is-using-dijkstra/?comment=28403#post-id-28403Answer by David Lu for <p>As an algorithm learner, I'm just curious about why <code>navfn</code> was is first equipped with <code>dijkstra</code> search algorith. <a href="http://answers.ros.org/question/11388/navfn-algorism?answer=16891#answer-container-16891">The answer at this question</a> explains how <code>navfn</code> works using <code>dijkstra</code>, but what is the reason it was selected instead of other algorithms that are equally good (e.g. <code>A*</code>) ?</p>
https://answers.ros.org/question/28366/why-navfn-is-using-dijkstra/?answer=73519#post-id-73519For completeness, I had the free cycles and I created an A* version here: https://github.com/ros-planning/navigation/tree/hydro-devel/global_plannerSat, 17 Aug 2013 09:29:30 -0500https://answers.ros.org/question/28366/why-navfn-is-using-dijkstra/?answer=73519#post-id-73519