加权二维阵列中两点之间的最短路径

Question

我在使最短路径算法正常工作时遇到问题。我有一个20 x 20的2d数组，其中包含表示城市之间道路的边权重。我没有得到城市间最短路径的正确结果。如有任何帮助，我们将不胜感激。

我的2d阵列看起来像：X轴=城市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算法，该算法可以在具有非负边wieghts的两个节点之间找到最短路径。

以下是打印的代码的工作版本：

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