Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

C/++/# Djikstra's algorithm with distance 1 between every node

Tags:
  1. Sep 25, 2016 #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 (Text):

            A  -   B  -  C
            \     /     /  \
             D    E    F    G
     
    the shortest path to F from A would be A -> B -> C -> F.
     
  2. jcsd
  3. Sep 25, 2016 #2
    Since your graph is effectively unweighted, you can use breadth first search to find the shortest path.
     
  4. Sep 26, 2016 #3

    Mark44

    Staff: Mentor

    Between it and what? The next node?
     
  5. Sep 28, 2016 #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 (Text):

    .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 (Text):

    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!");
            }
        }
    }
     
     
  6. Sep 28, 2016 #5

    Mark44

    Staff: Mentor

    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.

    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:
    There are eight possible directions from each node, not just the four that you show in the comment.
    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.
    Unclear. Better: The distance between each node and an adjacent node is 1.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Djikstra's algorithm with distance 1 between every node
  1. Ranking Algorithm (Replies: 22)

Loading...