# Djikstra's algorithm with distance 1 between every node

Does anyone know whether there exists a specialized Djikstra's algorithm for when every node has the same distance between it? Or to think of it another way, an algorithm for simply finding the minimum number of moves to get from 1 node to another?

e.g. in the following

Code:
        A  -   B  -  C
\     /     /  \
D    E    F    G

the shortest path to F from A would be A -> B -> C -> F.

Pepper Mint

Since your graph is effectively unweighted, you can use breadth first search to find the shortest path.

Mark44
Mentor
every node has the same distance between it
Between it and what? The next node?

Can someone help me figure out where I'm going wrong in my solution? It's failing some of the test cases and they're too big for me to possibly step through. The problem is basically that I'm given a matrix like

Code:
.X.X......X
.X*.X.XXX.X
.XX.X.XM...
......XXXX.

and have to move from the 'M' to the '*' along the '.' characters, where in a single move I can travel over any number of characters '.' in a single direction. The 'X' characters are obstructions.

My code is well-annotated. (The only confusing part may be that I transpose the original matrix so that I can access in the more natural [x,y] index structure instead of [y,x]).

Code:
using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;

// Algorithm explanation:
//
// Suppose we have a grid like
//
//       . . X
//       . . .
//       * X M
//
// Since we can travel along the the dots any distance in a
// single move, a graph of the possible moves is like
//
//          (0,0) -------- (1,0)
//          /   \            |
//         /     \           |
//       (0,2)---(0,1) --- (1,1)
//                 \        /
//                  \      /
//                   \    /
//                    (2,1)
//                    /
//                   /
//                 (2,2)
//
// where the distance between every node is 1. We're trying to get
// from node (2,2) to node (0,2) in the shortest route. We can use
// a BFS to find this route.

class Node
{
// coordinates
public int X { get; set; }
public int Y { get; set; }

// parent node
public Node Parent { get; set; } = null;

// distance from root node
public int Distance { get; set; } = Int32.MaxValue; // "infinity"

// nodes connected to this one
public List<Node> Neighbors { get; set; } = new List<Node>();
}

class ForbiddenForest
{
private Node[,] _tree;
private Node _start;
private Node _end;

public ForbiddenForest(char[,] mat)
{
BuildTree(mat);
}

// helper method for traversing a 2-D array
private static IEnumerable<T> MultiElements<T>(T[,] source)
{
for(int i = 0, n = source.GetLength(0); i < n; ++i)
for(int j = 0, m = source.GetLength(1); j < m; ++j)
yield return source[i, j];
}

private void BuildTree(char[,] mat)
{

int m = mat.GetLength(0),
n = mat.GetLength(1);

_tree = new Node[m, n];

// Add all the nodes to the tree with their x-y positions.
// Set the start and end nodes when we come across them.
for(int i = 0; i < m; ++i)
{
for(int j = 0; j < n; ++j)
{
switch(mat[i, j])
{
case '.':
_tree[i, j] = new Node() { X = i, Y = j };
break;
case 'M':
_tree[i, j] = new Node() { X = i, Y = j };
_start = _tree[i, j];
break;
case '*':
_tree[i, j] = new Node() { X = i, Y = j };
_end = _tree[i, j];
break;
}
}
}

var nodes = MultiElements(_tree).Where(z => z != null);

// Now add the neighbors. To do this, start at the node's x-y
// position on the graph and move as far possible up, right,
// down and left, collecting the nodes as we move along.
foreach(var node in nodes)
{
int x = node.X, y = node.Y;
// up:
while (--y >= 0 && _tree[x, y] != null)
// right:
y = node.Y;
while (++x < m && _tree[y, y] != null)
// down:
x = node.X;
while (++y < n && _tree[x, y] != null)
// left:
y = node.Y;
while (--x >= 0 && _tree[x, y] != null)
}

// Now fill in the Distance and Parent values by using the BFS
var Q = new Queue<Node>();

_start.Distance = 0;

Q.Enqueue(_start);

while(Q.Count > 0)
{
var current = Q.Dequeue();
foreach(var neighbor in current.Neighbors)
{
if(neighbor.Distance == Int32.MaxValue)
{
neighbor.Distance = current.Distance + 1;
neighbor.Parent = current;
Q.Enqueue(neighbor);
}
}
}

}

public int OptimalMoveNumbers { get { return _end.Distance; } }
}

class Solution
{
static void Main(String[] args)
{
for(int t = 0; t < T; ++t)
{
int[] line = Array.ConvertAll(Console.ReadLine().Split(' '), Int32.Parse);
int N = line[0], M = line[1];
char[,] matrix = new char[M,N];
for(int i = 0; i < N; ++i)
{
char[] row = Console.ReadLine().Where(c => c != ' ').ToArray();
for(int j = 0; j < M; ++j)
matrix[j,i] = row[j];
}
var ff = new ForbiddenForest(matrix);
Console.WriteLine(K == ff.OptimalMoveNumbers() ? "Impressed" : "Oops!");
}
}
}

Mark44
Mentor
Can someone help me figure out where I'm going wrong in my solution? It's failing some of the test cases and they're too big for me to possibly step through.
Then my advice is to try smaller examples, such as your 3 x 3 example you show in comments, or 4 x 4 or 5 x 5.

My code is well-annotated.
Debatable. Main() has no comments. Comments in Main() would help the reader understand what it is doing, especially in.the last two lines.
BuildTree could use some comments in the switch statement.
Also, in BuildTree, you have this comment:
// Now add the neighbors. To do this, start at the node's x-y
// position on the graph and move as far possible up, right,
// down and left,
There are eight possible directions from each node, not just the four that you show in the comment.
SlurrerOfSpeech said:
(The only confusing part may be that I transpose the original matrix so that I can access in the more natural [x,y] index structure instead of [y,x]).
IMO, the transpose is not really necessary. The matrix you show as your map example threw me off for a time, because the X in the upper right corner would be in row 0, column 2. IOW, the "natural" indexes of a 2-D matrix are in y, x form. As long as everyone understands your system, it's fine, though.
where the distance between every node is 1
Unclear. Better: The distance between each node and an adjacent node is 1.