Number of shortest paths between two coordinate points in a graph with constraints

Question

I have been given few coordinate points :

1. source (0,0)

2. destination (m,n)

3. a set of coordinate points S = {(x,y) such that 0 < x < m and 0 < y < n}

Objective is to find out the number of shortest paths between (0,0) and (m,n) such that any point in the set S is never encountered in these paths. How do i find it?

Answer 1

I think this is a complete solution, but you might want to test it and convert it to java.

The basic idea is to bread first search the grid. At each point in the grid, the number of ways of getting to that point is equal to the number of ways of getting next to that point in a distance one less.

n, m = 10, 15 #10 by 15 grid say

s = set([(1, 1), (2, 2), (9, 14)])

grid = []
ways = []
for i in range(n + 1):
    grid.append([None]*(m + 1))
    ways.append([0]*(m + 1))

start = (0, 0)
end = (n, m)

grid[0][0] = 0
ways[0][0] = 1

fringe = [start]
distance = 0
new_fringe = []
while True:
    for node in new_fringe:
        i, j = node
        deltas = [(-1, 0), (1, 0), (0, 1), (0, -1)] #directions to travel
        for di, dj in deltas:
            i2, j2 = i + di, j + dj
            if 0 <= i2 <= n and 0 <= j2 <= m and grid[i2][j2] == distance - 1:
                ways[i][j] += ways[i2][j2]

    new_fringe = []
    for node in fringe:
        i, j = node
        deltas = [(-1, 0), (1, 0), (0, 1), (0, -1)] #directions to travel
        for di, dj in deltas:
            i2, j2 = i + di, j + dj
            if 0 <= i2 <= n and 0 <= j2 <= m and (i2, j2) not in s and grid[i2][j2] is None:
                grid[i2][j2] = distance + 1
                new_fringe.append((i2, j2))
    if not new_fringe: #no new nodes
        break
    fringe = new_fringe
    distance += 1

for row in grid:
    print row
"""[[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15],
    [1, None, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16],
    [2, 3, None, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17],
    [3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18],
    [4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19],
    [5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20],
    [6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21],
    [7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22],
    [8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23],
    [9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, None, 24],
    [10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25]]"""

for row in ways:
    print row

"""[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
[1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14]
[1, 1, 0, 2, 5, 9, 14, 20, 27, 35, 44, 54, 65, 77, 90, 104]
[1, 2, 2, 4, 9, 18, 32, 52, 79, 114, 158, 212, 277, 354, 444, 548]
[1, 3, 5, 9, 18, 36, 68, 120, 199, 313, 471, 683, 960, 1314, 1758, 2306]
[1, 4, 9, 18, 36, 72, 140, 260, 459, 772, 1243, 1926, 2886, 4200, 5958, 8264]
[1, 5, 14, 32, 68, 140, 280, 540, 999, 1771, 3014, 4940, 7826, 12026, 17984, 26248]
[1, 6, 20, 52, 120, 260, 540, 1080, 2079, 3850, 6864, 11804, 19630, 31656, 49640, 75888]
[1, 7, 27, 79, 199, 459, 999, 2079, 4158, 8008, 14872, 26676, 46306, 77962, 127602, 203490]
[1, 8, 35, 114, 313, 772, 1771, 3850, 8008, 16016, 30888, 57564, 103870, 181832, 0, 203490]
[1, 9, 44, 158, 471, 1243, 3014, 6864, 14872, 30888, 61776, 119340, 223210, 405042, 405042, 608532]"""

Answer 2

Here you have a solution in C# but can converted easily to Java. Hopefully you will find it useful.

using System;
using System.Collections.Generic;
using System.Drawing;

namespace Game
{
    class Program
    {
        /// <summary>
        /// Find a matrix with all possible optimum paths from point A to point B
        /// </summary>
        /// <param name="rows">Rows of the matrix</param>
        /// <param name="cols">Cols of the matrix</param>
        /// <param name="points">Obstacles location</param>
        /// <param name="moves">Allowed moves</param>
        /// <param name="matrix">Resulting matrix</param>
        /// <param name="A">Starting point</param>
        /// <param name="B">Ending point</param>
        private static void FindMatrix(int rows, int cols, List<Point> points, List<Point> moves, out List<List<int>> matrix, out Point A, out Point B)
        {
            matrix = new List<List<int>>();
            A = new Point(-1, -1);
            B = new Point(-1, -1);
            //Init values of the matrix
            for (int row = 0; row <= rows; row++)
            {
                matrix.Add(new List<int>());
                for (int col = 0; col <= cols; col++)
                    matrix[matrix.Count - 1].Add(0);
            }
            var index = 0;
            while ((index < points.Count) && (points[index].Y >= 0) && (points[index].Y <= rows) && (points[index].X >= 0) && (points[index].X <= cols))
            {
                matrix[points[index].Y][points[index].X] = -1;
                index++;
            }
            if ((index == points.Count) && (matrix[0][0] == 0) && (matrix[rows][cols] == 0))
            {
                A.X = 0;
                A.Y = 0;
                B.X = cols;
                B.Y = rows;
            }
            if ((A.X >= 0) && (A.Y >= 0) && (B.X >= 0) && (B.Y >= 0)) //To check if points A and B exist in the board
            {
                var pairs = new List<Point>[2] { new List<Point>(), new List<Point>() };
                int level = 0;
                index = 0;
                pairs[index].Add(A);
                while ((pairs[index].Count > 0) && (pairs[index][pairs[index].Count - 1] != B))
                {
                    pairs[Math.Abs(1 - index)].Clear();
                    level++;
                    foreach (var pair in pairs[index])
                        foreach (var move in moves) //Test all possible moves
                            if ((pair.Y + move.Y >= 0) && (pair.Y + move.Y < matrix.Count) && (pair.X + move.X >= 0) && (pair.X + move.X < matrix[pair.Y + move.Y].Count) && (matrix[pair.Y + move.Y][pair.X + move.X] == 0)) //Inside the boundaries? Not visited before?
                            {
                                pairs[Math.Abs(1 - index)].Add(new Point(pair.X + move.X, pair.Y + move.Y));
                                matrix[pair.Y + move.Y][pair.X + move.X] = level;
                            }
                    index = Math.Abs(1 - index);
                }
                matrix[A.Y][A.X] = 0;
            }
        }

        /// <summary>
        /// Finds all possible optimum paths from point A to point B in a matix with obstacles
        /// </summary>
        /// <param name="matrix">Matrix with obstacles</param>
        /// <param name="moves">Allowed moves</param>
        /// <param name="A">Starting point</param>
        /// <param name="B">Ending point</param>
        /// <param name="result">Resulting optimum paths</param>
        /// <param name="list">Temporary single optimum path</param>
        private static void WalkMatrix(List<List<int>> matrix, List<Point> moves, Point A, Point B, ref List<List<Point>> result, ref List<Point> list)
        {
            if ((list.Count > 0) && (list[list.Count - 1] == B)) //Stop condition
            {
                result.Add(new List<Point>(list));
            }
            else
            {
                foreach (var move in moves)
                    if ((A.Y + move.Y >= 0) && (A.Y + move.Y < matrix.Count) && (A.X + move.X >= 0) && (A.X + move.X < matrix[A.Y + move.Y].Count) && (matrix[A.Y + move.Y][A.X + move.X] == matrix[A.Y][A.X] + 1)) //Inside the boundaries? Next step?
                    {
                        list.Add(new Point(A.X + move.X, A.Y + move.Y)); //Store temporary cell
                        WalkMatrix(matrix, moves, list[list.Count - 1], B, ref result, ref list);
                        list.RemoveAt(list.Count - 1); //Clean temporary cell
                    }
            }
        }

        public static List<List<Point>> FindPaths(int rows, int cols, List<Point> points)
        {
            var result = new List<List<Point>>();
            var moves = new List<Point> { new Point(1, 0), new Point(0, 1), new Point(-1, 0), new Point(0, -1) }; //Right, Down, Left, Up (clockwise)
            List<List<int>> matrix; //Matrix temporary representation to store all possible optimum paths
            Point A; //Starting point
            Point B; //Ending point
            FindMatrix(rows, cols, points, moves, out matrix, out A, out B);
            if ((A.X >= 0) && (A.Y >= 0) && (B.X >= 0) && (B.Y >= 0)) //To check if points A and B exist
            {
                List<Point> list = new List<Point>();
                list.Add(A);
                WalkMatrix(matrix, moves, A, B, ref result, ref list);
            }
            return result;
        }

        static void Main(string[] args)
        {
            var points = new List<Point>
            {
                new Point(3, 2),
                new Point(4, 2),
                new Point(5, 2),
                new Point(3, 3),
                new Point(4, 3),
                new Point(5, 3),
                new Point(3, 4),
                new Point(4, 4),
                new Point(5, 4)
            };
            List<List<Point>> paths = FindPaths(5, 10, points); //path.Count store the quantity of optimum paths
        }
    }
}

Answer 3

This can be solved using dynamic programming.

First, find the distance-to-origin of every node using a breadth-first search.

Then the number of shortest paths F that go through a point (x,y) with distance-to-origin d is just the sum of F(x1,y1) for all (x1, y1) neighboring (x,y) with distance d-1.

In other words, F(x,y) = Sum F(all neighboring points with distance-to-origin of d-1)

Answer 4

It can trivially be reduced to a graph problem if only integer coordinates is allowed.

This is how it is done in probably every game. The graph looks like a rectangle, source in one corner, destination in the opposite, and nodes are connected by vertical or horizontal edges. (Some nodes have been removed, the set S).

Now, shortest paths here are a subset of the Dyck-paths between the corners, so the Catalan numbers are an upper bound. http://mathworld.wolfram.com/DyckPath.html

Answer 5

I assume that you are talking about a grid of points defined in (x,y). And that between the two points where you want to calculate the set of shortest paths are a one of more obstacle(s)

So lets cut down the problem into two 1- Find a group of shortest paths from Point A to B 2- Make sure that on each path of these, none of the points belong to S are on the path

To solve this problem, there are many algorithms out there, the first one I'd think of is reinforcement learning This is a visual example to it in this link You can either use this library or implement it yourself. its fairly easy

Both algorithms could be implemented for a grid, where you mark some points as obstacles, i.e. your set of points S, and while detecting paths the points of set S will avoided.

Hope this helps

Answer 6

try to look at Dijkstra's algorithm: http://en.wikipedia.org/wiki/Dijkstra%27s%5Falgorithm