最小路徑算法

Question

我知道這並不完全是編程的問題，而是一個數學問題，而不是，但我會希望你有人能回答我:)

我正在尋找一種算法，讓我發現對面最小路徑n點，如果我知道所有點之間的所有距離。例如：我有12點（A，B，C，... H），我知道點之間的所有距離（AB，BC，...，GH，ecc ...）。如果我想從A到H，以最小路徑傳遞所有其他點，那麼我需要採取什麼方式？

我知道嘗試所有可能的方式，並選擇最短不是一個好方法（12點你有12個可能的方法，我需要使用這個算法超過12點......）但所有的我發現的其他算法太難理解了（比如Dijkstra）。

有人可以幫我解釋一種實現有用算法的方法嗎？我用Java編程，但我不知道我怎麼能寫下來的Dijkstra一個（我不明白），我沒有別的想法......

Answer 1

Traveling Salesman Problem.

這裏是我的解決方案（我知道我是蠻力，但我只是想分享我的解決方案）：

import java.io.BufferedReader; 
import java.io.IOException; 
import java.io.InputStreamReader; 
import java.util.Locale; 

import javax.swing.JSplitPane; 

/* VPW Template */ 

public class Main 
{ 

    /** 
    * @param args 
    */ 
    public static void main(String[] args) throws IOException 
    { 
     new Main().start(); 
    } 

    public float startX, startY; 
    public int cityCount; 
    public float citiesX[], citiesY[]; 
    public float distances[]; 
    public float shortest = Float.MAX_VALUE; 

    public void start() throws IOException 
    { 
     /* Read the stuff */ 
     BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); 
     String[] input = new String[Integer.parseInt(br.readLine())]; 
     cityCount = input.length; 
     citiesX = new float[input.length]; 
     citiesY = new float[input.length]; 
     for (int i = 0; i < input.length; ++i) 
     { 
      input[i] = br.readLine(); 
      String line = (input[i]); 
      String[] lineElements = line.split(" "); 
      float x = Float.parseFloat(lineElements[0]); 
      float y = Float.parseFloat(lineElements[1]); 
      citiesX[i] = x; 
      citiesY[i] = y; 
     } 
     /* Read current position */ 
     String line = (br.readLine()); 
     String[] lineElements = line.split(" "); 
     startX = Float.parseFloat(lineElements[0]); 
     startY = Float.parseFloat(lineElements[1]); 
     /* Compute distances */ 
     computeAllDistances(); 
     solve(); 
     System.out.println(String.format(Locale.US, "%.1f", shortest)); 
    } 

    public void solve() 
    { 
     for (int i = 1; i <= cityCount; ++i) 
     { 
      boolean[] wentTo = new boolean[cityCount]; 
      wentTo[i - 1] = true; 
      step(wentTo, i, distances[distanceIndex(0, i)]); 
     } 
    } 

    public void step(boolean[] wentTo, int currentCity, float distance) 
    { 
     int wentToCount = 0; 
     for (int i = 1; i <= cityCount; ++i) 
     { 
      if (wentTo[i - 1]) 
      { 
       ++wentToCount; 
       continue; 
      } 
      boolean[] copy = new boolean[cityCount]; 
      System.arraycopy(wentTo, 0, copy, 0, cityCount); 
      copy[i - 1] = true; 
      float dist = distance + distances[distanceIndex(currentCity, i)]; 
      step(copy, i, dist); 
     } 
     if (wentToCount == cityCount) 
     { 
      if (shortest > distance) 
      { 
       shortest = distance; 
      } 
     } 
    } 

    public void computeAllDistances() 
    { 
//  int count = (int) countDistances(cityCount + 1); 
//  System.out.println("Compute Distances (" + count + ")"); 
     distances = new float[cityCount * cityCount]; 
     for (int i = 0; i <= cityCount; ++i) 
     { 
      for (int j = i + 1; j <= cityCount; ++j) 
      { 
       float x1, y1, x2, y2; 
       if (i == 0) 
       { 
        x1 = startX; 
        y1 = startY; 
       } else 
       { 
        x1 = citiesX[i - 1]; 
        y1 = citiesY[i - 1]; 
       } 
       x2 = citiesX[j - 1]; 
       y2 = citiesY[j - 1]; 
       float xDiff = x1 - x2; 
       float yDiff = y1 - y2; 
       float dist = (float) Math.sqrt(xDiff * xDiff + yDiff * yDiff); 
//    System.out.printf("Distance (%d, %d)(%d) = %f\n", i, j, distanceIndex(i, j), dist); 
       distances[distanceIndex(i, j)] = dist; 
      } 
     } 
    } 

    public int distanceIndex(int c1, int c2) 
    { 
     if (c1 == c2) 
      throw new IllegalArgumentException("Cities are the same! (" + c1 + ")"); 
     if (c1 < c2) 
     { 
      return c1 * cityCount + c2 - 1; 
     } else 
     { 
      return c2 * cityCount + c1 - 1; 
     } 
    } 

    public long countDistances(long l) 
    { 
     if (l == 0 || l == 1) 
      return 0; 
     return (l - 1) + countDistances(l - 1); 
    } 

} 

用法：

輸入：

[number of cities] 
[x] [y]  (city 0) 
[x] [y]  (city 1) 
[x] [y]  (city 2) 
[x] [y]  (city 3) 
..... 
[x] [y]  (of your current position) 

輸出：

[The shortest distance you have to travel.] 

---

例子：

輸入：

11 
3 3 
7 1 
4 4 
2 10 
40 2 
15 9 
7 13 
16 23 
8 0 
4 8 
10 10 
5 10 

輸出：

83.2