Sign in to follow this  
ryt

How can I solve this problem to reach final point

Recommended Posts

Look at this picture: [url="http://img641.imageshack.us/i/pathz.jpg/"][img]http://img641.imageshack.us/img641/7779/pathz.jpg[/img][/url]

I need to start from point A and finish at same point. I have to choose ABCDEHGA route. Note that EH and HG are the same in magnitude as EF and EG. I thought to use Dijkstra's algorithm but that would get me to path ABCIJA or if that path would not exist it could not choose between previous two since they are same in magnitude. How can I pass that route? Is there some other algorithm?

Share this post


Link to post
Share on other sites
[quote name='ryt' timestamp='1302777079' post='4798334']
Look at this picture:
I need to start from point A and finish at same point. I have to choose ABCDEHGA route. Note that EH and HG are the same in magnitude as EF and EG. I thought to use Dijkstra's algorithm but that would get me to path ABCIJA or if that path would not exist it could not choose between previous two since they are same in magnitude. How can I pass that route? Is there some other algorithm?
[/quote]

Since this is not the optimal path and not the least optimal path (or rather not the only one), yo need to introduce some kind of differentation that will force the path to travel via H. You could modify Dijkstra's algorithm to skip paths without H traversed or you might want (though it's probably an overkill for this problem) to try a variation of A* - assign cost values for moving through specific points and make the H route as cheap as possible in comparison to others.

Share this post


Link to post
Share on other sites
I have thought to use Dijkstra's algorithm to skip the ones without H, but how can I know which ones I should skip? I need to create cycles that create faces so I can differentiate the faces in the rectangle. Whole problem is that user enters edges, and I have to create the faces based on what edges did the user create. So if user created AB and BC edges I have to create ABCDEHGA and ABCIJA faces. I have to choose the faces nearest to ABC that is not including FGHEF face.

Share this post


Link to post
Share on other sites
If that's the case then why does your path NEED to go through ABCDEHGA in this particular example? What's the generic condition for route plotting for this and any other set of edges that the user may enter?

Share this post


Link to post
Share on other sites
[quote name='Domx' timestamp='1302792565' post='4798417']
If that's the case then why does your path NEED to go through ABCDEHGA in this particular example? What's the generic condition for route plotting for this and any other set of edges that the user may enter?
[/quote]

Indeed. Dijkstra's Algorithm would return 0 steps given your start/stop requirement, regardless of the graph involved.

Share this post


Link to post
Share on other sites
[quote name='Domx' timestamp='1302792565' post='4798417']
If that's the case then why does your path NEED to go through ABCDEHGA in this particular example? What's the generic condition for route plotting for this and any other set of edges that the user may enter?
[/quote]

The path needs to go trough ABCDEHGA becase thats the new face, so the program would go through them and put them in the new face.

Share this post


Link to post
Share on other sites
I have solved it. Actualy when the user creates first face that face is saved. So when a user creates new edges the program should check in what face thouse edges are and loop trough only thouse face edges to create new faces.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this