Djikstra's algorithm with distance 1 between every node

  • #1
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.
 
  • Like
Likes Pepper Mint

Answers and Replies

  • #2
109
35
Since your graph is effectively unweighted, you can use breadth first search to find the shortest path.
 
  • #4
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)
                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!");
        }
    }
}
 
  • #5
35,115
6,856
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.
 

Related Threads on Djikstra's algorithm with distance 1 between every node

  • Last Post
Replies
1
Views
170
Replies
4
Views
760
Replies
0
Views
3K
  • Last Post
Replies
10
Views
4K
Replies
3
Views
2K
  • Last Post
Replies
16
Views
6K
  • Last Post
Replies
2
Views
2K
Replies
16
Views
2K
  • Last Post
Replies
2
Views
5K
  • Last Post
Replies
3
Views
2K
Top