# How can I solve this problem to reach final point

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

## Recommended Posts

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?

##### Share on other sites

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?

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 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 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 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?

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

##### 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?

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 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.

1. 1
Rutin
40
2. 2
3. 3
4. 4
5. 5

• 18
• 19
• 12
• 14
• 9
• ### Forum Statistics

• Total Topics
633362
• Total Posts
3011531
• ### Who's Online (See full list)

There are no registered users currently online

×