# A little confusion with A*

This topic is 5113 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

Does A* algorithm support -ve edges ? Apparently the pseudocode seem to support -ve edges to me ( the way nodes are removed from the "closed" list and put back into the "open list" ). But i have a little confusion here. Suppose we have a situation as below
A-->B-----------
|   ^          |
|   |------|   |
-------->  C <-|


[ sorry for the poor text-art ] A has an edge towards B and C, and B has a edge towards C, while C has a edge back towards B. Now, for example, A was popped out first in the algorithm; hence, both B and C will be pushed into the "Open List." Now Let B has the minimum "G" value hence B will be popped out next. Suppose now the edge between C-B is negative or maybe the G value of B becomes smaller as u travel from C to B. If this is the case, then B will be removed from the "Closed" list and put back into "Open" list. So , sometime in the future we will again process the node B and WOULDN'T this create an infinite cycle ? [ Because this time the cost to reach C will be smaller than the previous case and C will be again pushed into the "Open List" ] Someone please clear me out

##### Share on other sites
What do you mean by "-ve edges"? If you mean edges with negative cost, I don't think A* supports them.

##### Share on other sites
What would be the point of a negative cost anyways? Someone mind explaining that to me?

##### Share on other sites
A* supports negative-cost edges, but you'll need to pick your heuristic very carefully. Remember: you want a heuristic that NEVER overestimates the cost. If that heuristic fails to take into account the potential for a negative-cost edge, you will run into problems.

##### Share on other sites
DrEvil, a negative cost could represent some goodies that you can collect in some corridor. In the real world, some friends of mine bought a special train ticket that allowed them to travel through Europe for a month. Sometimes they took a train overnight that they didn't need to, so they could sleep in the train and not spend money in a hotel. That trip would have a negative cost.

Ahh gotcha

##### Share on other sites
Ok, Sneftel, but what about the possibility of INFINITE CYCLE, apparently it seems that like there COULD be INFINITE CYCLES if heuristics are not set carefully or if there are negative edges.

However, if we dont have negative edges [ letz just assume we are careful enough with the heuristic thingy ] then why should we bother about "Closed List." We can simply follow the Dijkstras method, ie. "Once a a node is popped ( relaxed ) , it's never relaxed again." Hence we dont have to worry about taking a node from the "Closed" list and putting in back into the "Open" list. Wouldn't that cut down on space and time requirement for the algorithm?

##### Share on other sites
Quote:
 Original post by brownyOk, Sneftel, but what about the possibility of INFINITE CYCLE, apparently it seems that like there COULD be INFINITE CYCLES if heuristics are not set carefully or if there are negative edges.
Yep. In those cases, there is no finite shortest-path, so the algorithm has trouble. I don't know of any pathfinding algorithms that correctly handle this situation (and I suspect that detecting all such negative loops is NP-complete).

##### Share on other sites
Instead of using negative costs, add the absolute value of the minimum node cost to all nodes such that all costs are greater than or equal to zero. It might not have the exactly same effect, but it should act simmilarly and would make things much easier to process (no need to worry about infinite loops, and there is a finite 'best path' if there is one at all).

##### Share on other sites
If you want to take rewards into account when performing pathfinding, then one method is to define a value function over possible paths. There was a good thread earlier this year on this exact problem, wherein I explained the procedure and provided one such function for use with A*.

Cheers,

Timkin

1. 1
2. 2
3. 3
Rutin
13
4. 4
5. 5

• 26
• 11
• 9
• 9
• 11
• ### Forum Statistics

• Total Topics
633700
• Total Posts
3013420
×