Самый короткий путь между двумя точками в взвешенном 2d массиве

Question

У меня проблемы с правильной работой алгоритма моего кратчайшего пути. У меня есть 2d-массив 20 x 20, который содержит граничные веса, представляющие дороги между городами. Я не получаю правильных результатов для кратчайшего пути между городами. Будем очень благодарны любой помощи.

Мой 2-й массив выглядит так: X-Axis = города 1-20, ось y = города 1-20.

X 732 X 212 X X X X X X X X X X X X X X 36 X 
66 X X X X X X X 111 X X 29 X X X X 65 X 14 X 
390 17 X X X X X X 11 X 38 X X 122 X X 211 78 X X 
X X 273 X 29 X X X X X X 42 X X X X X X X X 
X X X 122 X X X X 32 X X X X X X 12 X X X 102 
62 X X X 211 X X 132 X X X 871 X X X X X X X X 
20 200 X 41 X X X X X X 122 X 81 11 X X X X X X 
X X 210 X X 5 X X X X X X X X X 74 X X X X 
X 95 X X X X 120 X X X 2 X X X X X X X X 11 
X X 925 X X X X X X X X 121 X X X X X X X 653 
X 81 X 90 X X X X X X X 219 X X X 211 X X X X 
X X 11 X 98 X 122 390 X X X X X X X X 121 X 122 X 
719 X X X X X X X 9 X X X X X X X 26 X X 832 
X X 22 X X X X X 13 182 X X X X X X X X X 219 
X X X X X 22 X X X X X X X X X X X X X X 
X X X X X X X X X X 73 X X X X X X 98 X X 
77 X X X X X X X 200 X 21 93 X X X X X X X 190 
X X X X X X X 29 X 33 X X X X 33 940 X X X 121 
X 322 X X 74 219 X X X 111 X X X X X X X X X X 
X X X X X X X X X X X X X X X X X X X X 

Вот мой код до сих пор:

public static void distance(){ 
    ArrayList<String> path = new ArrayList<String>(); 
    ArrayList<Integer> total = new ArrayList<Integer>(); 

    int shortest = 10000; // temp value for testing 
    int temp; 
    int totalDistance = 0; 

    int shortNum = 0; // The city code for the next shortest path 

    String code = ""; //The city code 
    Scanner sc = new Scanner(System.in);  
    System.out.println("\nCity codes: "); 
    String d = sc.nextLine(); 
    d = d.toUpperCase(); 
    String[]command = d.split(" "); 
    if (command.length != 2){ 
     System.out.println("You must enter 2 city codes."); 
     return; 
    } 
    String fromCity = command[0]; 
    String toCity = command[1]; 

    int fCity = find(fromCity); 
    int tCity = find(toCity); 
    fCity = fCity -1; 
    tCity = tCity -1; 
    int p = fCity; 
    String shortCode; 
    if (fCity == tCity){ 
     System.out.println("The distance from " + cities[fCity][2] + " to " + 
          cities[tCity][2] + " is 0"); 
    } 

    else { 

     while(shortNum != tCity){ 
     for (int i = 0; i < 20; i ++){ 
      if (roads[p][i] != "X"){ 
       temp = Integer.parseInt(roads[p][i]); 
       if (temp < shortest){ 
        shortest = temp; 
        shortNum = i; 
        code = cities[i][1]; 

        System.out.println(code); 
        //p = i; 
       }   
      } 
     } 
     path.add(code); 
     total.add(shortest); 
     p = shortNum; 
     shortest = 10000; 
    } 
     System.out.println("The path is" + path); 
     for (int k = 0; k < total.size(); k ++){ 
      totalDistance += total.get(k); 
     } 

     System.out.println("Total distance is " + totalDistance); 
    } 
} 

Для кратчайшего пути между городами 1 и 2 моя программа дает мне полную дистанцию ​​276. Идущий через 19, 5, 16, 11

Правильное решение - общее расстояние 225. Путь должен быть 19, 5, 9, 11

Может ли кто-нибудь увидеть, где я поступил не так?

Заранее благодарю за любую помощь.

Answer 1

По существу, вы должны следить за кратчайшими путями к всех городам от узлаисточника с каждой итерацией. В настоящее время вы отслеживаете только самый короткий путь между соседними городами от Текущий город (temp переменная) с каждой итерацией. Это не даст общий кратчайший путь.

Вы хотите использовать Djistra's algorithm, который находит кратчайший путь между двумя узлами с неотрицательными границами.

Ниже приводится рабочая версия кода, который печатает:

// City 1 => 2 (all indices start from 0) 
City[0] => City[1] 
// Path: 1 => 19 => 5 =>9 => 11 => 2 
Path:[0, 18, 4, 8, 10, 1] 
// The distance you give is incorrect, it's 36+74+32+2+81 = 225 
Distance:225 

(я вынимают все пользовательского ввода, и используются целые числа вместо строк для массива дорог).

static int[][] roads = 
    {{-1, 732, -1, 212, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 36, -1}, 
    {66, -1, -1, -1, -1, -1, -1, -1, 111, -1, -1, 29, -1, -1, -1, -1, 65, -1, 14, -1}, 
    {390, 17, -1, -1, -1, -1, -1, -1, 11, -1, 38, -1, -1, 122, -1, -1, 211, 78, -1, -1}, 
    {-1, -1, 273, -1, 29, -1, -1, -1, -1, -1, -1, 42, -1, -1, -1, -1, -1, -1, -1, -1}, 
    {-1, -1, -1, 122, -1, -1, -1, -1, 32, -1, -1, -1, -1, -1, -1, 12, -1, -1, -1, 102}, 
    {62, -1, -1, -1, 211, -1, -1, 132, -1, -1, -1, 871, -1, -1, -1, -1, -1, -1, -1, -1}, 
    {20, 200, -1, 41, -1, -1, -1, -1, -1, -1, 122, -1, 81, 11, -1, -1, -1, -1, -1, -1}, 
    {-1, -1, 210, -1, -1, 5, -1, -1, -1, -1, -1, -1, -1, -1, -1, 74, -1, -1, -1, -1}, 
    {-1, 95, -1, -1, -1, -1, 120, -1, -1, -1, 2, -1, -1, -1, -1, -1, -1, -1, -1, 11}, 
    {-1, -1, 925, -1, -1, -1, -1, -1, -1, -1, -1, 121, -1, -1, -1, -1, -1, -1, -1, 653}, 
    {-1, 81, -1, 90, -1, -1, -1, -1, -1, -1, -1, 219, -1, -1, -1, 211, -1, -1, -1, -1}, 
    {-1, -1, 11, -1, 98, -1, 122, 390, -1, -1, -1, -1, -1, -1, -1, -1, 121, -1, 122, -1}, 
    {719, -1, -1, -1, -1, -1, -1, -1, 9, -1, -1, -1, -1, -1, -1, -1, 26, -1, -1, 832}, 
    {-1, -1, 22, -1, -1, -1, -1, -1, 13, 182, -1, -1, -1, -1, -1, -1, -1, -1, -1, 219}, 
    {-1, -1, -1, -1, -1, 22, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, 
    {-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 73, -1, -1, -1, -1, -1, -1, 98, -1, -1}, 
    {77, -1, -1, -1, -1, -1, -1, -1, 200, -1, 21, 93, -1, -1, -1, -1, -1, -1, -1, 190}, 
    {-1, -1, -1, -1, -1, -1, -1, 29, -1, 33, -1, -1, -1, -1, 33, 940, -1, -1, -1, 121}, 
    {-1, 322, -1, -1, 74, 219, -1, -1, -1, 111, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}, 
    {-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1}}; 


public static List<Integer> shortestPath(int fCity, int tCity){ 
    // keep track of the distance and path from source to all nodes 
    Map<Integer, Integer> distToSource = new HashMap<Integer, Integer>(20); 
    Map<Integer, Integer> paths = new HashMap<Integer, Integer>(20); 

    // initialize the distance to source for all nodes 
    distToSource.put(fCity, 0); 
    for(int i=0; i<20; i++) 
     if(i != fCity) 
      distToSource.put(i,Integer.MAX_VALUE); 

    // start at source and find shortest path to destination 
    int shortest_index = fCity, shortest_dist, edge; 
    while(shortest_index != tCity){ 
     shortest_dist = Integer.MAX_VALUE; 
     shortest_index = -1; 
     // find shortest path from all options in distToSource 
     for(Map.Entry<Integer, Integer> e : distToSource.entrySet()){ 
      if(e.getValue() < shortest_dist){ 
       shortest_dist = e.getValue(); 
       shortest_index = e.getKey(); 
      } 
     } 

     // no path to destination 
     if(shortest_index < 0) 
      return null; 

     //remove the shortest node 
     distToSource.remove(shortest_index); 

     //update all edges out of node 'shortest_index' 
     for(Integer i : distToSource.keySet()){ 
      edge = roads[shortest_index][i]; 
      if (edge > 0 && shortest_dist + edge < distToSource.get(i)){ 
       distToSource.put(i, shortest_dist + edge); 
       paths.put(i, shortest_index); 
      } 
     } 
    } 

    // create path by working backwards from destination to source 
    Deque<Integer> path = new ArrayDeque<Integer>(); 
    path.add(shortest_index); 
    while(paths.containsKey(shortest_index)){ 
     path.addFirst(paths.get(shortest_index)); 
     shortest_index = paths.get(shortest_index); 
    } 

    return new ArrayList<Integer>(path); 
} 

public static int distance(List<Integer> path){ 
    int dist = 0; 
    for(int i=0; i<path.size()-1; i++) 
     dist += roads[path.get(i)][path.get(i+1)]; 
    return dist; 
} 

public static void main(String[] args) { 
    int fCity = 0, tCity = 1; 
    List<Integer> path = shortestPath(fCity, tCity); 
    System.out.println("City["+ fCity + "] => City[" + tCity + "]"); 
    System.out.println("Path:" + path); 
    System.out.println("Distance:" + distance(path)); 
}