Pathfinding or pathing is the plotting of the shortest route between two points. It is a more practical variant on solving mazes. This field of research is based heavily on Dijkstra's algorithm for finding the shortest path on a weighted graph.
1
vote
0answers
40 views
NBA*: Very efficient bidirectional heuristic search algorithm in Java
I have implemented NBA* (New Bidirectional A*) in Java and compared it against conventional A* and Dijkstra algorithms. The results may be as optimistic as this:
Seed = 8900460676230
Created the ...
4
votes
1answer
65 views
BFS shortest path
I have the following code to return the shortest path on a matrix from top left corner to bottom right corner, with the option of removing one of wall cells (marked ...
8
votes
2answers
92 views
2D grid Hamiltonian path puzzle solver
The puzzle goes like this: in a rectangular 2D grid there are empty spaces (.), exactly one starting point (S, ...
6
votes
3answers
685 views
Using a greedy algorithm to find the best path in a 2D array
I'm a student and this is one of my assignments. My professor basically confirmed that my code is correct but all he grades on is if I finished the assignment correctly but not the coding style. I ...
5
votes
0answers
105 views
Percolation Model
Newbie here, presenting the code for close public scrutiny.
Couple remarks regarding the context (taken from Princeton's COS 226 course):
In this problem I model a percolation system using an N-by-...
3
votes
1answer
81 views
Optimisation of A* in C++
I'm working on an A* pathfinding algorithm to solve a programming problem, and part of the constraint is the runtime. I need to find a path in a 2D grid with blocked or non-blocked tiles. You can't ...
1
vote
0answers
41 views
Thread pool based unweighted path finder in Java for graphs with slow expansion operator
Introduction
Given a directed unweighted graph, the objective of this library is to find a shortest path from a given source node to a given target node. Clearly, one candidate algorithm to find ...
4
votes
1answer
75 views
A* Algorithm speed improvement
Currently I have a very general purpose A* algorithm, which I've submitted as open sourced at https://github.com/kd7uiy/AStar . I've been trying to speed it up for the last month or so, and while I'm ...
4
votes
1answer
72 views
Pathfinder from image file
I've created a simple pathfinder programme that receives its input from a very small .png file.
Example file here:
Here's a link to the file (note that the green pixel represents the start, the red ...
2
votes
0answers
77 views
Dijkstra's single source shortest path algorithm (with Fibonacci heap)
I implemented a generic Dijkstra algorithm. It's lazy since the vertices with their final distances are request on demand. I used the Fibonacci Heap from this question with a few changes (added a copy ...
2
votes
1answer
62 views
Weighted graph and pathfinding implementation in C#
I am implementing fundamental data structures in C#. I have written a weighted graph in Java so my main motivation here is to sharpen my skills in C#. I have tested with various cases and there seems ...
1
vote
0answers
16 views
Wikipath stack in Java - Part II/IV - The implicit Wikipedia article graph
This question is the continuation of the Wikipath stack series: the two classes that - given a Wikipedia article \$A\$ - return the lists of neighbour articles. The forward node expander return the ...
11
votes
3answers
141 views
Dijkstra's algorithm in C99
I just implement Dijkstra's algorithm in C99. Can you review my code please? I'm looking for any mistake, performance improvement or coding style errors.
main.c
...
3
votes
1answer
50 views
Matlab implementation of Needleman-Wunsch algorithm
This code (an implementation of the path finding Needleman-Wunsch algorithm), given two sequences, correctly aligns and calculates the similarity of them. For example, given two sequences:
AAA,CCC
...
0
votes
1answer
132 views
Shortest path via two intermediate points
My code takes a long time for big graphs.
How can I make it faster?
I'm trying to calculate the shortest path for 3 path's using queue but for big input my program crashes.
I'm stuck here. Can ...
0
votes
0answers
38 views
Finding shortest paths in a Wikipedia article graph using Java - second attempt
I have improved Finding shortest paths in a Wikipedia article graph using Java.
Now I have this:
AbstractWikipediaShortestPathFinder.java:
...
4
votes
1answer
124 views
Dijkstra's algorithm
Assuming everything else works as expected, is the following a correct - but not the most efficient way - of implementing Dijkstra algorithm? Because I have tested it on several examples and it gives ...
4
votes
1answer
101 views
Algorithms to find various kinds of paths in graphs
I think many here are familiar with the graph data structure. Not very long ago, I implemented as an exercise a supposedly simple Graph application that does some traversals. To note, the most complex ...
1
vote
1answer
132 views
3
votes
1answer
214 views
Dijkstra's algorithm: traditional and bidirectional in Python
I have translated Dijkstra's algorithms (uni- and bidirectional variants) from Java to Python, eventually coming up with this:
Dijkstra.py
...
3
votes
1answer
110 views
MazeRunner in Java - follow-up
I've refined a lot of the code from my previous question, and have also decided to include the logic that interprets a given text file. Any advice on how to improve the actual algorithm that solves ...
3
votes
1answer
150 views
MazeRunner in Java
To test the queue I perfected from one of my CR questions, I've developed a maze program that receives an input maze, starting and end positions, and solves it. I have separate software that handles ...
4
votes
1answer
249 views
Finding the longest path, avoiding obstacles in a 2D plane
The Scenario
You are given a matrix of size m x n (width x height) with m*n spots where there are a few obstacles. Spots with obstacles are marked as 1, and those without are marked as 0. You can ...
0
votes
2answers
63 views
Check if path exists directed graph, without using collection
I have written code to find whether the path exists between source and destination in a directed graph. I have used BFS and instead of ArrayList or queue. I have ...
6
votes
1answer
154 views
Shortest knight path
In preparing a review of this question, I decided to rewrite the code from scratch using a more object oriented approach as I suggested in my review.
To recapitulate the problem statement, we are ...
2
votes
1answer
93 views
Finding smallest number of moves
We are given a map of sides of length n and m (both n and m are less than 1000), divided into n*m fields (squares of side 1). The map looks (for example) like this:
...
6
votes
1answer
181 views
A* algorithm in C# for use in a game
I recently started up again on a 2D game engine I have been working on over the last couple of years. I managed to implement a version of the a* algorithm that seems to work fine for my game, but it ...
8
votes
1answer
626 views
Path finding algorithm using recursion in Python
Here is a code I developed some time ago. I wonder if there is anything I can do to improve it. It works for non-loopy mazes which was already my goal.
In the maze defined, ...
1
vote
2answers
258 views
Traversing a stack in my DFS algorithm for finding a path in a maze
I am trying to get this code running as fast as possible when traversing through my stack of my DFS currently the input files are like so:
...
0
votes
1answer
254 views
k-shortest path algorithm in Java
This snippet is about computing \$k\$ shortest paths in a directed graph using this algorithm.
I would like to hear about API design, naming/coding conventions, and so on.
My implementation follows:
...
7
votes
1answer
136 views
Attempt at Dijkstra's algorithm
I tried to implement Dijkstra algorithm in C++ 11. Is this a good implementation of Dijkstra algorithm in C++ or not? I have overloaded -= and ...
3
votes
2answers
200 views
Djikstra's algorithm in Clojure
I'm learning Clojure and I'm interested in areas that could be more idiomatic. The main function is below. If you're interested in the whole lib, check out this.
The function operates on a ...
14
votes
6answers
532 views
“Simple” pathfinding algorithm
I decided to write a pathfinding algorithm in order to expose myself to the world of pathfinding and for me to further understand more advanced algorithms such as A*. I chose C# due to its flexibility ...
6
votes
3answers
877 views
Handling a maze in JavaScript
Is there a way to shorten the conditional statement below? As you can see, there's a lot of repetition. Is the if-statement the best approach here? Bearing in mind ...
3
votes
2answers
99 views
2D A* Path-Finder
I have re-coded my entire path-finding class, it used to follow Dijkstra's Algorithm, while also being super inefficient, using Lists and a lot of other bad things that I had/have no idea about.
...
5
votes
1answer
91 views
Comparing puzzle solvers in Java
I have this program that solves a \$(n^2 - 1)\$-puzzles for general \$n\$. I have three solvers:
BidirectionalBFSPathFinder
...
0
votes
1answer
44 views
Groovy pathfinding algorithm
I have created a bit of path-finding code in response to this code golf question. Since this is one of my first large bits of code in Groovy that I have written, I would like to see how I could ...
0
votes
0answers
312 views
Floyd-Warshall algorithm and a tiny all-pairs shortest path library in Java
Now I have implemented the Floyd-Warshall algorithm with emphasis on dropping space complexity from \$\Theta(V^3)\$ to \$\Theta(V^2)\$. Also, I tried hard to make the API as logical as possible. What ...
2
votes
1answer
220 views
BFS for modified shortest path
Given K descriptions for bus line paths that exists to lead students between N campuses. What is the minimum cost that a student will have to goes from campus 1 to campus N ?
The itinerary of ...
7
votes
1answer
251 views
“Dungeon Game” solution
The demons had captured the princess (P) and imprisoned her in the
bottom-right corner of a dungeon. The dungeon consists of M x N rooms
laid out in a 2D grid. Our valiant knight (K) was initially ...
2
votes
1answer
88 views
Shortest path from U to V using at most k nodes
I'm trying to solve a problem that asks for a shortest path between two cities with at most k nodes.
The first line of input has the number of test cases. On the second line 3 integers are given, ...
6
votes
1answer
141 views
Live Graphical Demonstation of a Breadth-First Search Algorithm
As a first step to making a PacMan clone, I wrote a Breadth-First Search demonstration that updates itself live as you draw walls and drag around the start and end points. It was inspired by the site ...
1
vote
1answer
262 views
Shortest path on a maze with keys and doors
The locks of the doors present in the maze are of 7 types: A, B, C, D, E, F and G. There are also some copies of keys around the maze, which can be of types a, b, c, d, e, f or g. A key of type a ...
-1
votes
1answer
81 views
1
vote
0answers
476 views
Brute force shortest path in Java
I had to ask myself a couple years ago: before Edsger Dijkstra invented his famous shortest path algorithm, how brute force approach would seem. Below is my version. It's super slow, but I find it ...
4
votes
2answers
469 views
Maze solver for 2D matrix in Ruby
I got rejected for a junior Ruby job entry where I had to solve a 2D matrix as a maze with walls.
This is the main class:
solver.rb
...
4
votes
2answers
1k views
Path sum in binary tree
Root to leaf path sum equal to a given number
Given a binary tree and a number, return true if the tree has a root-to-leaf path such that adding up all the values along the path equals the given ...
2
votes
0answers
247 views
A simple graph walk interception algorithm in Java
I have that girl whose graph walk I want to intercept, but because I am not good at running algorithms in my head, I had to program my computer to do that for me. I would not consider the problem to ...
-1
votes
1answer
159 views
A* pathfinder in C
Now I have this implementation of A*. Basically it is the same as the Dijkstra's algorithm in my previous post, yet I bothered to make it more cohesive by making functions for handling all the state ...
4
votes
1answer
96 views
Dijkstra's shortest path algorithm in C
Now I have this C implementation of the famous algorithm:
dijkstra.h:
...
