Dijkstra’s Algorithm For Path Finding Problems

March 29, 2017

The blog is migrated to https://thiloshon.wordpress.com

The path finding is one of the most common problems found in computer science, especially in game development and AI. The problem has been analyzed, scrutinized and dissected by various people and several possible solutions and algorithms have been implemented. The important part is not to implement one by ourselves but to understand what each does and how its effective from one another. In the CW, this is exactly what’s expected. You don’t necessarily have to implement the best solution. You just have to implement one and understand how efficient it is. I.e. derive the growth rate. It can be a slow algorithm. If its slow say its slow and justify why its slow. Derive the growth rate and support your rationale.

I’m using the Dijkstra’s Algorithm in this blog to find the shortest distance path. Don’t be intimidated by the name of the Algorithm, its fairly simple one. It uses Greedy Algorithm with a simple tweak and is okayishly fast. Might not work effectively in large datasets with lots of blocks but that’s fine for now.

I’m using the StdDraw library provided in the ‘Algorithms, Part II’ Coursera Course by Princeton University and few additional code from the course.

Alright, enough with the prepping, lets dive in. First let’s see if the algorithm makes sense.

Dijkstra’s Algorithm starts from the start node and checks for the best node surrounded by it. In our case the shortest distance node. It moves to that node and from that node checks the best node surrounded. Moves to that node. It does this repeatedly. Until it finds the destination. That’s it. Theory done, Class dismissed.

Dry Run

This is a sample grid with three blocks, Let’s find shortest distance from start on (0,0) to end on (4,2).

The demo is done with Euclidean Distances in mind. So horizontal path gets the value 1 and diagonal paths get 1.4.

First we define the distance of start as 0 and all other grids as infinity.

From the start grid, we set the minimum distance of the surrounding grids. The horizontal grid distance is 1. One is less than infinity. So we set 1 as distance of horizontal values. The diagonal value is 1.4. 1.4 is less than infinity. So we set diagonal grids’ distance as 1.4. Meanwhile we add the visiting nodes to a priority queue prioritized by the lesser distance value. And also we define the parent nodes of each node from which the minimum value was taken.

Once we find all node distances around the start node we set start node as ‘visited’. We won’t check visited nodes again.

Then we take the top node from the priority queue and change values surrounding that node. Here we add the distance of the current node to the value when finding distance to surrounding nodes.

At the end of 2^nd node the values and parents are like this.

Then take the node from priority queue and do the same.

And again.

At the end of that iteration the values and parents are as follows.

Then we take the node from priority queue and do yet again.

And again.

You keep doing this until you hit the end node.

Once you get to the end node, trace back the parent nodes from the end to find the path. The distance is already found.

So that is how you find the shortest path in a grid.

The Code

/*************************************************************************

* Author: Thiloshon Nagarajah

* Created: 12-Dec-16

* Last update: 29-03-2017

* Path Finding using Dijkstra in Euclidean Distance

*************************************************************************/

import java.util.*;

public class Dijkstra {

Node start;

Node end;

Node[][] gridArea;

// Horizontal and VerticalDistance

double hVDistance = 1.0;

// Diagonal Distance

double dDistance = 1.4;

/* for Manhattan Distances,

double horizontalVerticalDistance = 1.0;

double diagonalDistance = 2.0;

for Chebyshev Distances,

double horizontalVerticalDistance = 1.0;

double diagonalDistance = 1.0; */

/**

* @param matrix The boolean matrix from the framework given

* @param si start x value

* @param sj start y value

* @param ei end x value

* @param ej end x value

* @return The path nodes

ArrayList<Node> distance(boolean[][] matrix, int si, int sj, int ei, int ej) {

int size = matrix.length;

start = new Node(si, sj);

end = new Node(ei, ej);

// The grid that is used to store nodes

gridArea = new Node[size][size];

// Creating nodes and finding blocked cells in matrix and mapping accordingly to our grid

for (int i = 0; i < size; ++i) {

for (int j = 0; j < size; ++j) {

gridArea[i][j] = new Node(i, j);

if (matrix[i][j] == false) {

gridArea[i][j].blocked = true;

}

// setting start distance to 0.

// All other nodes will have infinity distance at the beginning

start.distance =0;

// a comparator object to deal with Priority Queue

Comparator<Node> adjacencyComparator = (left, right) -> {

if (left.distance > (right.distance)) {

return 1;

}

return -1;

};

// Queue to store visiting nodes

Queue<Node> queueB = new PriorityQueue(size, adjacencyComparator);

queueB.add(start);

while (queueB.size() > 0) {

Node current = queueB.remove();

Node t;

// Top

if (current.x - 1 >= 0) {

// Top Top

t = gridArea[current.x - 1][current.y];

if (!t.visited && !t.blocked && t.distance > current.distance + hVDistance) {

t.distance = current.distance + hVDistance;

t.parent = current;

queueB.add(t);

}

// Top Left

if (current.y - 1 > 0) {

t = gridArea[current.x - 1][current.y - 1];

if (!t.visited && !t.blocked && t.distance > current.distance + dDistance) {

t.distance = current.distance + dDistance;

t.parent = current;

queueB.add(t);

}

// Top Right

if (current.y + 1 < size) {

t = gridArea[current.x - 1][current.y + 1];

if (!t.visited && !t.blocked && t.distance > current.distance + dDistance) {

t.distance = current.distance + dDistance;

t.parent = current;

queueB.add(t);

}

// Left

if (current.y - 1 > 0) {

t = gridArea[current.x][current.y - 1];

if (!t.visited && !t.blocked && t.distance > current.distance + hVDistance) {

t.distance = current.distance + hVDistance;

t.parent = current;

queueB.add(t);

}

// Right

if (current.y + 1 < size) {

t = gridArea[current.x][current.y + 1];

if (!t.visited && !t.blocked && t.distance > current.distance + hVDistance) {

t.distance = current.distance + hVDistance;

t.parent = current;

queueB.add(t);

}

// Down

if (current.x + 1 < size) {

// Down Down

t = gridArea[current.x + 1][current.y];

if (!t.visited && !t.blocked && t.distance > current.distance + hVDistance) {

t.distance = current.distance + hVDistance;

t.parent = current;

queueB.add(t);

}

// Down Left

if (current.y - 1 >= 0) {

t = gridArea[current.x + 1][current.y - 1];

if (!t.visited && !t.blocked && t.distance > current.distance + dDistance) {

t.distance = current.distance + dDistance;

t.parent = current;

queueB.add(t);

}

// Down Right

if (current.y + 1 < size) {

t = gridArea[current.x + 1][current.y + 1];

if (!t.visited && !t.blocked && t.distance > current.distance + dDistance) {

t.distance = current.distance + dDistance;

t.parent = current;

queueB.add(t);

}

current.visited = true;

}

ArrayList<Node> path = new ArrayList<>();

// Checking if a path exists

if (!(gridArea[end.x][end.y].distance == Integer.MAX_VALUE)) {

//Trace back the path

Node current = gridArea[end.x][end.y];

while (current.parent != null) {

path.add(current.parent);

current = current.parent;

}

} else System.out.println("No possible path");

return path;

}

class Node {

int x;

int y;

double distance = Integer.MAX_VALUE;

Node parent = null;

boolean visited;

boolean blocked;

public Node(int x, int y) {

this.x = x;

this.y = y;

}

Integrating with the StdDraw framework

The framework randomly generates a 2 dimensional boolean array to store the grid. We have to pass this array as the parameter to our algorithm.

ArrayList<Dijkstra.Node> path = new Dijkstra().distance(randomlyGenMatrix, Ai, Aj, Bi, Bj);

This would return an Arraylist of Nodes of the minimum distance path.

All we have to do now is to draw the path in the grid given. Probably in a different color.

StdDraw.setPenColor(Color.RED);

for (Dijkstra.Node node : path) {

StdDraw.circle(node.y, size - node.x - 1, .5);

}

You have to repeat all these for three different distances.

Notes

The framework given prints nodes in a weird manner. If you try to print a circle in first column second row (1,0), it actually prints at the bottom.

The three distances in question, Manhattan, Chebyshev and Euclidean can easily be integrated in the algorithm. All you have to do, is to set
horizontalVerticalDistance as 1
diagonalDistance as 2
to get Manhattan Distance and
horizontalVerticalDistance as 1
diagonalDistance as 1
to get Chebyshev Distance.

These path finding problem can easily mapped to graph problems too. Consider the nodes as vertex and imaginary edges between them. The various distances will be the weight of the edges. This would help in finding the growth rate of the algorithm.