Shortest route between multiple points

Question

I need to find the shortest route between multipe points. Let's say that I have these four points:

var startPoint = new Point(1, 1);
var pointsToGoPast = new List<Point> { new Point(3,1); new Point(2,4); };
var endPoint = new Point(10, 10);

So, I want to find out which points to go past first, in order to get the shortest route, from startPoint to endPoint.

Can anyone help me?

Update: It has to go past each of the points in the pointsToGoPast list. The cost is even for each route.

Answer 1

You can do this by Dijkstra's Algorithm.

Sample project with code here

The only thing that needs to change is the weights in the project, since the weight is based off of distance between the two points. (So you need to modify the Location to store a Point and the Connection to calculate the weight (distance) in the constructor.

Wikipedia has a very nice article on the algorithm

Answer 2

Dijkstra's algorithm

class Dijkstra
{        
        private int rank = 0;
        private int[,] L;
        private int[] C; 
        public int[] D;
        private int trank = 0;
        public Dijkstra(int paramRank,int [,]paramArray)
        {
            L = new int[paramRank, paramRank];
            C = new int[paramRank];
            D = new int[paramRank];
            rank = paramRank;
            for (int i = 0; i < rank; i++)
            {
                for (int j = 0; j < rank; j++) {
                    L[i, j] = paramArray[i, j];
                }
            }

            for (int i = 0; i < rank; i++)
            {
                C[i] = i;
            }
            C[0] = -1;          
            for (int i = 1; i < rank; i++)
                D[i] = L[0, i];
        }
        public void DijkstraSolving()
        {            
            int minValue = Int32.MaxValue;
            int minNode = 0;
            for (int i = 0; i < rank; i++)
            {
                if (C[i] == -1)
                    continue;
                if (D[i] > 0 && D[i] < minValue)
                {
                    minValue = D[i];
                    minNode = i;
                }
            }
            C[minNode] = -1;
            for (int i = 0; i < rank; i++)
            { 
                if (L[minNode, i] < 0)
                    continue;
                if (D[i] < 0) {
                    D[i] = minValue + L[minNode, i];
                    continue;
                }
                if ((D[minNode] + L[minNode, i]) < D[i])
                    D[i] = minValue+ L[minNode, i];
            }
        }
        public void Run()
        {
            for (trank = 1; trank >rank; trank++)
            {
                DijkstraSolving();
                Console.WriteLine("iteration" + trank);
                for (int i = 0; i < rank; i++)
                    Console.Write(D[i] + " ");
                Console.WriteLine("");
                for (int i = 0; i < rank; i++)
                    Console.Write(C[i] + " ");
                Console.WriteLine("");                
            }
        }
 }

Answer 3

As has already been pointed out, it is not clear what the cost is of going from one point to another point. Is it just the distance between those points? Anyway, regardless, such a problem can be solved using conventional Linear Programming. I've just finished making a C# library to simplify shortest path problems. Downloadable here.

There is still more work to do on this library, but it should give you what you want in a very simple manner.

Regards,

Bruce.

Answer 4

Can be solved simply if you have SQL server

select geography :: Point(@PointALatitude, @PointALongitude, 4326).STDistance(geography::Point(@PointBLatitude, @PointBLongitude, 4326))

Result is returned in meters so just divide by 1000 for Km or 1609.344 for Miles