Share your knowledge at the LQ Wiki.
Go Back > Forums > Non-*NIX Forums > Programming
User Name
Programming This forum is for all programming questions.
The question does not have to be directly related to Linux and any language is fair game.


  Search this Thread
Old 04-21-2007, 02:07 PM   #1
Registered: Sep 2006
Posts: 374

Rep: Reputation: 16
Algorithm to find paths

I'm trying to find the name of algorithms to find ways. For example, suppose that i'm in a labyrinth, and i want to find the exit.

- How can i build an algorithm to find the exit path, from several possibilities?
- Exists a right algorithm?
- What's the name of the algorithm?

Old 04-21-2007, 02:08 PM   #2
Registered: Sep 2006
Posts: 374

Original Poster
Rep: Reputation: 16
Sorry, this isn't the right questions.

One of the answer for this is Dijkstra's algorithm.
Old 04-21-2007, 02:19 PM   #3
Registered: Sep 2006
Posts: 374

Original Poster
Rep: Reputation: 16
What i'm asking is:

For example, i've the following labyrinth in an array of Strings:

The x marks the initial position. The '.' marks a path. The '#' is a wall.

1 - Know, i want to transform the labyrinth, to a form that i can apply an algorithm like the Dijkstra's algorithm.

Can anybody help me?

2 - Count the number of faces of the wall from the labyrinth. The problem is that, in only counts the wall that can be reachable from the exit. Ie, the path that is unreachable, doesn't count.

Can anybody help me?

If you answer to this question, you don't need to write code or pseudocode. Just tell me what should i do.

Old 04-21-2007, 04:32 PM   #4
Registered: Oct 2005
Posts: 970

Rep: Reputation: Disabled
Dijkstra is not the correct algorithm for this as it's a greedy algorithm and normally used when X's position is not know, instead you want to use A*.

When areas are unreachable they should be marked as such, so that algorithm does not try every node possible.

[edit]X does not mean x as you have it just some position like your exit.
Here is a good tutorial on the algorithm

Last edited by dmail; 04-21-2007 at 04:41 PM.
Old 04-21-2007, 04:46 PM   #5
Senior Member
Registered: Oct 2003
Location: UK
Distribution: Kubuntu 12.10 (using awesome wm though)
Posts: 3,530

Rep: Reputation: 63
Dijkstra's walk might not be suitable because it is expensive (although it will find the best path). An alternative is A*, which is popular in games because it is generally much cheaper.

A good paper on path finding can be found here.
Old 04-24-2007, 02:18 AM   #6
Senior Member
Registered: Nov 2005
Location: Hanoi
Distribution: Fedora 13, Ubuntu 10.04
Posts: 2,379

Rep: Reputation: 148Reputation: 148
To answer your question about how to transform the maze. You want to express the problem as a graph. Each point on the maze is a node and the path is set up from node A to node B if there is a path in your maze. The number of faces of the wall will be 4 - the number of paths from that node.

I hope that makes sense. If you require a better explanation just shout


Thread Tools Search this Thread
Search this Thread:

Advanced Search

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is Off
HTML code is Off

Similar Threads
Thread Thread Starter Forum Replies Last Post
token bucket algorithm vs Leaky bucket algorithm xeon123 Linux - Networking 2 03-26-2007 04:57 AM
Wine can't find paths in Mandriva 2005 LE kalahari875 Mandriva 3 06-28-2005 07:22 AM
Where can I find source code for CPRM algorithm? George2 Programming 2 03-13-2004 04:06 AM
Automatically resolving WINDOWS paths to pre-configured Linux paths gazzy Linux - General 1 09-05-2003 10:15 PM
assistance with an algorithm mandrake_linux Programming 3 07-27-2001 04:03 AM > Forums > Non-*NIX Forums > Programming

All times are GMT -5. The time now is 11:09 AM.

Main Menu
Write for LQ is looking for people interested in writing Editorials, Articles, Reviews, and more. If you'd like to contribute content, let us know.
Main Menu
RSS1  Latest Threads
RSS1  LQ News
Twitter: @linuxquestions
Facebook: linuxquestions Google+: linuxquestions
Open Source Consulting | Domain Registration