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.

you can move from any point to any point directly? Whats the cost between 2 points? I would go with the http://en.wikipedia.org/wiki/Dijkstra's_algorithm — Imre L, Jun 03 '12 at 22:42
Dijkstra solved this problem back in the sixties. He's gone now, you'll have to apply his algorithm yourself: http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm — Hans Passant, Jun 03 '12 at 22:44
Do you want to visit each point, or just find the shortest path? Shortest path is easier, to visit every point is much harder. Search for the Travelling Salesman problem for an overview of the complexity. — TheEvilPenguin, Jun 03 '12 at 23:57
Possible duplicate of [Calculating the shortest route between two points](http://stackoverflow.com/questions/39256309/calculating-the-shortest-route-between-two-points) — Alex Filatov, Sep 08 '16 at 20:12

score 6 · Accepted Answer · answered Jun 03 '12 at 22:44

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

score 3 · Answer 2 · answered Jun 03 '12 at 23:28

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("");                
            }
        }
 }

score 3 · Answer 3 · answered Jul 29 '13 at 04:05

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.

score 2 · Answer 4 · answered Oct 18 '13 at 09:12

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

Shortest route between multiple points

4 Answers4

Linked

Related