Djikstra's algorithm with distance 1 between every node

[SlurrerOfSpeech]

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

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

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

 

[Jaeusm]

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

 

[Mark44]

every node has the same distance between it

Between it and what? The next node?

 

[SlurrerOfSpeech]

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

.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]).

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)
                node.Neighbors.Add(_tree[x, y]);
            // right:
            y = node.Y;
            while (++x < m && _tree[y, y] != null)
                node.Neighbors.Add(_tree[x, y]);
            // down:
            x = node.X;
            while (++y < n && _tree[x, y] != null)
                node.Neighbors.Add(_tree[x, y]);
            // left:
            y = node.Y;
            while (--x >= 0 && _tree[x, y] != null)
                node.Neighbors.Add(_tree[x, y]);
        }

        // Now fill in the Distance and Parent values by using the BFS
        // algorithm on https://en.wikipedia.org/wiki/Breadth-first_search
        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)
    {
        int T = Int32.Parse(Console.ReadLine());
        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];
           }
           int K = Int32.Parse(Console.ReadLine());
           var ff = new ForbiddenForest(matrix);
           Console.WriteLine(K == ff.OptimalMoveNumbers() ? "Impressed" : "Oops!");
        }
    }
}

 

[Mark44]

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.

(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.