# Tagged Questions

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.

1answer
29 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 ...
1answer
119 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 ...
0answers
36 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: ...
1answer
116 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 ...
1answer
99 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 ...
1answer
96 views

### Shortest path in maze

Please help review my code. ...
1answer
135 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 ...
1answer
103 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 ...
1answer
98 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 ...
1answer
179 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 ...
2answers
61 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 ...
1answer
114 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 ...
1answer
88 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: ...
1answer
164 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 ...
1answer
381 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, ...
2answers
184 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: ...
1answer
211 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: ...
1answer
134 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 ...
2answers
187 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 ...
6answers
492 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 ...
3answers
870 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 ...
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. ...
1answer
86 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 ...
1answer
41 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 ...
0answers
267 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 ...
1answer
186 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 ...
1answer
197 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 ...
1answer
80 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, ...
1answer
125 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 ...
1answer
236 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 ...
1answer
79 views

### 2D A* path finder

How can I improve the speed of this path finder A* implementation? ...
0answers
350 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 ...
2answers
416 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 ...
2answers
879 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 ...
0answers
209 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 ...
1answer
148 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 ...
1answer
90 views

### Dijkstra's shortest path algorithm in C

Now I have this C implementation of the famous algorithm: dijkstra.h: ...
1answer
749 views

### IDA*: Iterative Deepening A* implementation

I created a generic version of IDA*. I am attempting to create the following code with exceptional quality and performance. I'm hoping to try and create short code tutorials regarding. However, the ...
3answers
449 views

### SPOJ solution of GRAVITY

I am solving problem GRAVITY on SPOJ. Each test case is a rectangular ASCII grid of dimensions m × n, and you have to determine ...
1answer
226 views

### Racetrack pathfinding and path following

Racetrack The August community challenge is to implement a program that plays the Racetrack game. Each player starts with an integer position on a square grid. On each turn, the current player can ...
1answer
257 views

### Shortest path in dag saga: Dijkstra's algorithm [closed]

I have this Dijkstra's shortest path algorithm: net.coderodde.graph.pathfinding.AbstractWeightedPathFinder: ...
2answers
449 views

### Let's (path) find A Star

Yesterday I found myself struggling with creating an A * algorithm in Java, but this morning I finally figured it out, so I would love to hear what Code Review has to say about it! The goal here is ...
1answer
268 views

### Shortest path in image

This code takes an image and detects a global shortest path from the top to bottom row, with the requirement that top and bottom column index be the same. For this, it scans through each element on ...
2answers
188 views

### A* algorithm in C++

I wanted to know if my A* algorithm is well-implemented and if it could be optimized in any way. ...
1answer
260 views

### Shortest paths from a single source (Dijkstra and Bellman-Ford)

I did not implement a priority queue in Dijkstra. I'm not sure if a trivial priority queue is the best choice, since, after each iteration, several elements change their value. Maybe it is better to ...
2answers
90 views

### Obstacle-avoiding AI

I have made a game in Java that involves two players to fight each other with spaceships. For one player mode, I have programmed a simple AI to avoid allies and asteroids and go straight towards the ...
2answers
58 views

### Simple Grid Builder for Future Maze Applications

I'm new to Clojure and decided to read the book, "Mazes for Programmers". My first task, without reading any of the book, was to think of how I would create a maze. This is my first result and I'd ...
2answers
272 views

### Memory efficient A* (AStar) Algorithm

I am writing a solved for 15 puzzle game which will find the solution path to any NxN board. For easier boards the algorithm works great solving almost any 3x3 boards, most 4x4 boards, but when I go ...
0answers
97 views

### Golang A* Pathfinder

This is a generalized A* pathfinder in Go. I am new to the language and am eager for advice about best practices. In particular, I am not sure if the type assertion I make in ...
2answers
129 views

### Pathfinding in turn-based strategy game

I am using Python with libtcodpy to build a turn-based strategy game. In this game each unit has a maximum range which varies from 4-10. This range determines how many "steps" the unit can take and ...