Convert Distance between points to Point

Question

Given a start point and a distance, calculate the destination point. I have a Matrix with customers and it's distance between each other. (See link jsfiddle)

Matrix: http://jsfiddle.net/j69kA/

How can i convert it's corrects to Coordinate Points (X, Y) based on Center Point ? Which can be 1.

    1   2   3   4   5   6   7   8   9   10
1   0   24  15  27  19  16  11  33  28  30
2   24  0   28  32  29  17  20  20  27  30
3   15  28  0   19  22  12  22  29  29  15
4   27  32  19  0   29  23  13  31  20  28
5   19  29  22  29  0   24  25  17  22  23
6   16  17  12  23  24  0   22  23  21  12
7   11  20  22  13  25  22  0   28  23  19
8   33  20  29  31  17  23  28  0   28  22
9   28  27  29  20  22  21  23  28  0   25
10  30  30  15  28  23  12  19  22  25  0

Answer 1

What you are trying to do is unfortunately impossible.

Why?

Because there is more than one set of points which would produce the distance matrix above.

To prove this, just imagine you had a map of points, whose distances corresponded to that matrix.

Now reflect this map in the Y axis. The relative distances are all unchanged => different point map, same matrix!

Now reflect this map in the X axis. The relative distances are all unchanged => different point map, same matrix!

Now rotate it 90 degrees. Again, the distances are unchanged => same matrix again!

You see the pattern here?

In fact, there are an infinite number of possible sets of X,Y points that could produce the matrix of distances you show above.

In short, there's not a one-to-one mapping. It's many-to-one. You throw away valuable information when you go from a set of points to a distance matrix, and you can't get it back afterwards.

If you just want to get the shortest path between points (and don't care about the co-ordinate system), then Dijkstra’s algorithm is what you need.

In your case you have direct distances between every point, but might want to see if an indirect path would be shorter. In that case, the following console app (just written and largely untested except with your data) should do what you want:

namespace DijkstraTest
{
    class Node
    {
        public Node(int index)
        {
            distanceFromStart = -1;
            this.index = index;
        }

        public int distanceFromStart;
        public bool visited;
        public Node parent;
        public int index;
    }

    class Dijkstra
    {
        private int[,] distanceMatrix;
        private int size;

        public Dijkstra(int[,] distanceMatrix)
        {
            this.distanceMatrix = distanceMatrix;
            size = distanceMatrix.GetLength(0);
            if (distanceMatrix.Rank != 2 || (size != distanceMatrix.GetLength(1)))
                throw new ArgumentException("Matrix must be 2-D and square!");
        }

        public List<Node> GetShortestPath(int startPos, int endPos)
        {
            var nodes = Enumerable.Range(0, size).Select(i => new Node(i)).ToList();
            nodes[startPos].distanceFromStart = 0;
            var endNode = nodes[endPos];

            while (!endNode.visited)
            {
                var currentNode = nodes.Where(i => !i.visited && i.distanceFromStart != -1)
                                       .OrderBy(i => i.distanceFromStart).First();

                foreach (var neighbour in nodes
                             .Where(i => !i.visited && distanceMatrix[currentNode.index, i.index] != -1))

                {
                    var thisDistance = currentNode.distanceFromStart +
                                       distanceMatrix[currentNode.index, neighbour.index];

                    if (neighbour.distanceFromStart == -1 || neighbour.distanceFromStart > thisDistance)
                    {
                        neighbour.distanceFromStart = thisDistance;
                        neighbour.parent = currentNode;
                    }
                }
                currentNode.visited = true;
            }

            // build the results working back
            var retVal = new List<Node> {endNode};

            while (endNode.parent != null)
            {
                endNode = endNode.parent;
                retVal.Add(endNode);
            } 

            retVal.Reverse();
            return retVal;
        }
    }

    class Program
    {
        static int[,] DistanceMatrix = {{-1,   24,  15,  27,  19,  16,  11,  33,  28,  30},
                                        {24,  -1,   28,  32,  29,  17,  20,  20,  27,  30},
                                        {15,  28,  -1,   19,  22,  12,  22,  29,  29,  15},
                                        {27,  32,  19,  -1,   29,  23,  13,  31,  20,  28},
                                        {19,  29,  22,  29,  -1,   24,  25,  17,  22,  23},
                                        {16,  17,  12,  23,  24,  -1,   22,  23,  21,  12},
                                        {11,  20,  22,  13,  25,  22,  -1,   28,  23,  19},
                                        {33,  20,  29,  31,  17,  23,  28,  -1,   28,  22},
                                        {28,  27,  29,  20,  22,  21,  23,  28,  -1,   25},
                                        {30,  30,  15,  28,  23,  12,  19,  22,  25,  -1}};

        static void Main(string[] args)
        {
            var dijkstra = new Dijkstra(DistanceMatrix);

            for (int i = 0; i < 10; i++)
            {
                for (int j = i; j < 10; j++)
                {
                    var path = dijkstra.GetShortestPath(i, j);
                    // print complex paths that are shorter than just going straight there...
                    if (path.Count > 2)
                    {
                        Console.Write("From {0} to {1}: ", i,j);
                        foreach (var item in path)
                        {
                            Console.Write(" {0} ", item.index);
                        }
                        Console.WriteLine(": Total distance: {0}, Direct distance: {1}", 
                            path.Last().distanceFromStart, DistanceMatrix[i,j]);
                    }
                }
            }
        }
    }

It's quite rough-and-ready, but it seems to produce sensible output. Using your distance matrix, you get the following output (indirect paths that are shorter that direct):

From 0 to 3:  0  6  3 : Total distance: 24, Direct distance: 27
From 0 to 9:  0  5  9 : Total distance: 28, Direct distance: 30
From 1 to 9:  1  5  9 : Total distance: 29, Direct distance: 30

It's based on the Wikipedia article here, translated directly to C#.

Answer 2

To build a cartesian system you require two points -> origin, destination

Your matrix contains only the distance between two points and not the origin and destination.

You are required to convert this to Cartesian System (using XY plane).

You say the origin is 1.

How would you propose this system to be, since it cant be Cartesian because in that case you want Destination points to.

I suggest use polar coordinate system, with equal angle between two points.

Edit: From http://www.c-program-example.com/

Use :

#include "stdio.h"
#define infinity 999

void dij(int n,int v,int cost[10][10],int dist[])
{
  int i,u,count,w,flag[10],min;
  for(i=1;i<=n;i++)
        flag[i]=0,dist[i]=cost[v][i];
  count=2;
  while(count<=n)
  {
        min=99;
        for(w=1;w<=n;w++)
              if(dist[w]<min && !flag[w])
                    min=dist[w],u=w;
        flag[u]=1;
        count++;
        for(w=1;w<=n;w++)
              if((dist[u]+cost[u][w]<dist[w]) && !flag[w])
                    dist[w]=dist[u]+cost[u][w];
  }
}

void start()
{
  int n,v,i,j,cost[10][10],dist[10];
  printf("\n Enter the number of nodes:");
  scanf("%d",&n);
  printf("\n Enter the cost matrix:\n");
  for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
        {
              scanf("%d",&cost[i][j]);
                    if(cost[i][j]==0)
              cost[i][j]=infinity;
        }
  printf("\n Enter the source matrix:");
  scanf("%d",&v);
  dij(n,v,cost,dist);
  printf("\n Shortest path:\n");
  for(i=1;i<=n;i++)
        if(i!=v)
              printf("%d->%d,cost=%d\n",v,i,dist[i]);
}