Algorithm for a "map"

Question

Well, I was trying to solve the following problem: Suppose I have a "map of a city." I have a source and a destination. There are streets that are blocked and streets that are free. Wanted to create an algorithm to tell me which path to take to get to the destination, passing through the streets that are free.

example:

S - Source 
D - Destination 
F - Free Streets 
B - Busy Streets 

B B B B B 
S F F F B 
F B B F F 
F F B B D 
B F F F F

In this case, would have two possible routes:

B B B B B 
S - - - B 
* B B - - 
* * B B D 
B * * * *

Was thinking of doing the following:

Make a function to check whether the directions were free. If for example the east is free, the function would create a thread with the new coordinates, x and y + 1 and so on, would create a thread for each direction in each "point". I do not know if this is the best way, but was wondering if someone can give an idea of some other way to do!

Was thinking of doing in python, because I'm more familiar with the language. I'm just doing it as a hobby.

I think this question belongs to Programmers Stack Exchange - http://programmers.stackexchange.com/ However, if you have already made an attempt at coding this problem and hitting an issue, please post the code so that people can take a look. — shaktimaan, Aug 08 '14 at 19:24
Ok thank you! I even started to develop the code, but was wondering if there is any more "intelligent" way to do. — Jorge Rossi, Aug 08 '14 at 19:29
nodes and edges, you should look at graphs http://en.wikipedia.org/wiki/Graph_theory — Padraic Cunningham, Aug 08 '14 at 19:36
[See this answer](http://stackoverflow.com/a/15534662/298607) — dawg, Aug 08 '14 at 19:44

Raghav RV · Answer 1 · 2014-08-08T19:43:56.547

4

These type of problems fall under routing algorithm. Refer to Dijikstra's shortest path finding algorithm.

Since your input is an array ( Map ), you could do Depth first search on it to determine connected points that make up a path.

If you are looking for efficient ways to implement this, you might want to take a look at networkx library. Refer here for pre implemented traversal methods in networkx.

edited Aug 08 '14 at 19:43

answered Aug 08 '14 at 19:33

Raghav RV

3,938
2
22
27

score 0 · Answer 2 · answered Aug 08 '14 at 19:47

there are some algorithms for solving this problem ! so in this case and depending on your python tag i suggest use Numpy mudule in python ! this is an example for you that isn't the complete answer but might be a point ! and i hope be helpful :

import numpy 
x = numpy.array([['B', 'B', 'B', 'B', 'B',], 
['S', 'F', 'F', 'F', 'B'], 
['B', 'B', 'B', 'F', 'F'], 
['B', 'F', 'B', 'B', 'D'], 
['B', 'F', 'F', 'F', 'F']])
#print numpy.where(x == 'F')[0]
numpy.place(x, x=='F', ['-'])

print x

result :

[['B' 'B' 'B' 'B' 'B']
 ['S' '-' '-' '-' 'B']
 ['B' 'B' 'B' '-' '-']
 ['B' '-' 'B' 'B' 'D']
 ['B' '-' '-' '-' '-']]

Algorithm for a "map"

2 Answers2