多點之間的最短路線

-3

我需要找到多點之間的最短路線。比方說，我有這四點：多點之間的最短路線

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);

所以，我想找出它指向晃過第一，爲了獲得最短的路線，從到的startPoint端點。

任何人都可以幫助我嗎？

更新：它必須通過pointsToGoPast列表中的每個點。每條路線的費用均勻。

來源

2012-06-03 Martin

您可以從任何位置移動到直接任意一點？ 2點之間的成本是多少？我會去http://en.wikipedia.org/wiki/Dijkstra's_algorithm –

Dijkstra在六十年代解決了這個問題。他現在走了，你必須自己應用他的算法：http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm –

你想訪問每個點，或只是找到最短路徑？最短路徑比較容易，訪問每一個點都比較困難。搜索旅行商問題以瞭解複雜程度的概述。 – TheEvilPenguin

你可以通過Dijkstra的算法做到這一點。

Sample project with code here

需要改變的唯一事情是在項目的權重，因爲權重是基於關閉兩點之間的距離。（所以你需要修改Location來存儲Point和Connection在構造函數來計算權重（距離）。

Wikipedia has a very nice article on the algorithm

來源

2012-06-03 22:44:41 justderb

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

來源

2012-06-03 23:28:24

正如已經指出的那樣，不清楚從一個點到另一個點的成本是多少？它只是這些點之間的距離嗎？無論如何，無論如何，使用傳統的線性規劃都可以解決這樣的問題我剛剛完成了一個C＃庫以簡化最短路徑問題。可下載here。

這個庫還有更多的工作要做，但它應該以非常簡單的方式給你想要的東西。

Regards，

Bruce。

來源

2013-07-29 04:05:49

可以簡單解決的，如果你有SQL服務器

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

結果是米返回所以僅僅通過1000公里或1609.344劃分爲萬里

來源

2013-10-18 09:12:17 Lloydz1

多點之間的最短路線

回答

相關問題