Finding the shortest path between two points on a grid, using Haskell.

Posted by esperantist on Stack Overflow See other posts from Stack Overflow or by esperantist
Published on 2010-03-15T23:09:24Z Indexed on 2010/03/15 23:29 UTC
Read the original article Hit count: 688

Filed under:

haskell

|

shortest-path

|

functional

This is a problem that I can easily enough solve in a non-functional manner.

But solving it in Haskell is giving me big problems. Me being inexperienced when it comes to functional programming is surely a reason.

The problem:

I have a 2D field divided into rectangles of equal size. A simple grid. Some rectangles are empty space (and can be passed through) while others are impassable. Given a starting rectangle A and a destination rectangle B, how would I calculate the shortest path between the two? Movement is possible only vertically and horizontally, in steps a single rectangle large.

How would I go about accomplishing this in Haskell? Code snippets certainly welcome, but also certainly not neccessary. And links to further resources also very welcome!

Thanks!

© Stack Overflow or respective owner

Related posts about haskell

Learning Haskell: How to remove an item from a List in Haskell

as seen on Stack Overflow - Search for 'Stack Overflow'
Trying to learn Haskell. I am trying to write a simple function to remove a number from a list without using built-in function (delete...I think). For the sake of simplicity, let's assume that the input parameter is an Integer and the list is an Integer list. Here is the code I have, Please tell me… >>> More
Using Data.Heap in Haskell, or reading Haskell docs for a beginner

as seen on Stack Overflow - Search for 'Stack Overflow'
I'm trying to use Haskells Data.Heap module, but I'm incapable of even using it with integers. The only heap I've been capable of using is "empty", which does not take any arguments. Later on I'll figure out how to instance for my needs, but for now I'd be glad if I was even able to test it with… >>> More
What kind of things are easy in Haskell and hard in Scala, and vice versa?

as seen on Programmers - Search for 'Programmers'
There has been some intermingling of Scala and Haskell communities, and I have noticed now and then people commenting on stuff that's supposed to be easy in Haskell and hard and Scala. Less often (maybe because I read Scala questions, not Haskell ones), I see someone mentioning that something in Scala… >>> More
Haskell's cabal dependency problem with happy

as seen on Programmers - Search for 'Programmers'
I have problems installing ghc-mod on my linux machine. cabal worries about "happy" not being available in versione = 1.17: $ cabal install ghc-mod Resolving dependencies... [1 of 1] Compiling Main ( /tmp/haskell-src-exts-1.14.0-1357/haskell-src-exts-1.14.0/Setup.hs, /tmp/haskell-src-exts-1… >>> More
Understanding Haskell's fibonacci

as seen on Stack Overflow - Search for 'Stack Overflow'
fibs :: [Int] fibs = 0 : 1 : [ a + b | (a, b) <- zip fibs (tail fibs)] This generates the Fibonacci sequence. I understand the behaviour of the guards, of :, zip and tail, but I don't understand <-. What is it doing here? >>> More

Related posts about shortest-path

Algorithm shortest path between all points

as seen on Stack Overflow - Search for 'Stack Overflow'
Hi, suppose I have 10 points. I know the distance between each point. I need to find the shortest possible route passing trough all points. I have tried a couple of algorithms (Dijkstra, Floyd Warshall,...) and the all give me the shortest path between start and end, but they don't make a route… >>> More
Shortest-path algorithms which use a space-time tradeoff?

as seen on Stack Overflow - Search for 'Stack Overflow'
I need to find shortest paths in an unweighted, undirected graph. There are algorithms which can find a shortest path between two nodes, but this can take time. There are also algorithms for computing shortest paths for all pairs of nodes in the graph, but storing such a lookup table would take lots… >>> More
C# - Shortest path map finding

as seen on Stack Overflow - Search for 'Stack Overflow'
I try to write a simple program in C#, it's like map finding . I've a picture of city / or district ( it's const ) and I'll add a database to this program to store variables, points . I use floyd to find the shortest path and I'll draw the path in the image ( by coordinates I think ) . This is the… >>> More
search all paths and the shortest path for a graph - Prolog

as seen on Stack Overflow - Search for 'Stack Overflow'
Hi , I have a problem in my code with turbo prolog wich search all paths and the shortest path for a graph between 2 nodes the problem that i have is to test if the node is on the list or not exactly in the clause of member and this is my code : /* 1 ---- b ---- 3 … >>> More
Dijstra shortest path algorithm with edge cost.

as seen on Stack Overflow - Search for 'Stack Overflow'
Hello, I have a directed, positive weighted graph. Each edge have a cost of use. I have only A money, i want to calculate shortest paths with dijkstra algorithm, but sum of edges costs on route must be less or equal to A. I want to do this with most smallest Dijstra modification (if I can do it… >>> More