Java中二维数组的Dijkstra算法

Dijkstra algorithm for 2D array in Java

提问by Stan

This is for a school project; I'm running into a huge amount of trouble, and I can't seem to find a understandable solution.

这是一个学校项目；我遇到了很多麻烦，我似乎无法找到一个可以理解的解决方案。

   a b c d e z
 a - 2 3 - - -
 b 2 - - 5 2 -
 c 3 - - - 5 -
 d - 5 - - 1 2
 e - 2 5 1 - 4
 z - - - 2 4 -

That's the two dimensional array. So if you want to find the shortest path, its from a,b,e,d,z = 7, and (a,b) = (b,a) -- it takes you to the new row to for the row's adjacent paths

这就是二维数组。所以如果你想找到最短的路径，它来自 a,b,e,d,z = 7, and (a,b) = (b,a) - 它会带你到新行到该行的相邻路径

Is there anyone that can help me implement Dijkstra's algorithm for this example? I'd really appreciate it. (I seem to like arrays best, maps and sets confuse me a bit, lists are manageable -though I'm willing to look into any sort of solution at this point)

有没有人可以帮助我为这个例子实现 Dijkstra 算法？我真的很感激。（我似乎最喜欢数组，映射和集合让我有点困惑，列表是可管理的 - 尽管此时我愿意研究任何类型的解决方案）

[At least I'm not just ripping off a source from the net. I actually wanna learn these things... It's just really hard (>.<)]

[至少我不只是从网上窃取资源。我其实很想学这些东西...真的很难 (>.<)]

Oh, start point is A and end point is Z

哦，起点是A，终点是Z

---

---

As most people, I don't find the concept of the algorithm difficult -- I just can see to get the coding right... Help please?

与大多数人一样，我不觉得算法的概念很难——我只是可以看到正确的编码......请帮忙？

Sample code-- a friend helped me with this a lot (though its filled with data structures that I find difficult to follow) I"ve also tried adapting the C++ code from dreamincode.net/forums/blog/martyr2/index.php?showentry=578 into java, but that didn't go so well ...

示例代码——一位朋友在这方面帮了我很多（尽管其中充满了我发现难以理解的数据结构）我还尝试改编来自 dreamincode.net/forums/blog/martyr2/index.php 的 C++ 代码？ showentry=578 进入 Java，但进展并不顺利...

import java.util.*;

public class Pathy{

    private static class pathyNode{
        public final String name;
        public Map<pathyNode, Integer> adjacentNodes;

        public pathyNode(String n){
            name = n;
            adjacentNodes = new HashMap<pathyNode, Integer>();
        }

    }

    //instance variables

    //constructors

    //accessors

    //methods
    public static ArrayList<pathyNode> convert(int[][] inMatrix){
        ArrayList<pathyNode> nodeList = new ArrayList<pathyNode>();
        for(int i = 0; i < inMatrix.length; i++){
            nodeList.add(new pathyNode("" + i));
        }
        for(int i = 0; i < inMatrix.length; i++){
            for(int j = 0; j < inMatrix[i].length; j++){
                if(inMatrix[i][j] != -1){
                    nodeList.get(i).adjacentNodes.put(nodeList.get(j),
                            new Integer(inMatrix[i][j]));
                }
            }
        }
        return nodeList;
    }

    public static Map<pathyNode, Integer> Dijkstra(ArrayList<pathyNode> inGraph){
        Set<pathyNode> visited = new HashSet<pathyNode>();
        visited.add(inGraph.get(0));
        pathyNode source = inGraph.get(0);
        Map answer = new TreeMap<pathyNode, Integer>();
        for(pathyNode node : inGraph){
            dijkstraHelper(visited, 0, source, node);
            answer.put(node, dijkstraHelper(visited, 0, source, node));
        }
        return answer;
    }

    private static int dijkstraHelper(Set<pathyNode> visited, int sum, pathyNode start, pathyNode destination){
        Map<pathyNode, Integer> adjacent = new HashMap<pathyNode, Integer>();

        for(pathyNode n : visited){
            for(pathyNode m: n.adjacentNodes.keySet()){
                if(adjacent.containsKey(m)){
                    Integer temp = n.adjacentNodes.get(m);
                    if(temp < adjacent.get(m)){
                        adjacent.put(m, temp);
                    }
                }
                else{
                    adjacent.put(m, n.adjacentNodes.get(m));
                }
            }
        }

        Map<pathyNode, Integer> adjacent2 = new HashMap<pathyNode, Integer>();
        Set<pathyNode> tempSet = adjacent.keySet();
        tempSet.removeAll(visited);
        for(pathyNode n: tempSet){
            adjacent2.put(n, adjacent.get(n));
        }
        adjacent = adjacent2;
        Integer min = new Integer(java.lang.Integer.MAX_VALUE);
        pathyNode minNode = null;

        for(pathyNode n: adjacent.keySet()){
            Integer temp = adjacent.get(n);
            if(temp < min){
                min = temp;
                minNode = n;
            }
        }
        visited.add(minNode);
        sum += min.intValue();
        sum = dijkstraHelper(visited, sum, start, destination);
        return sum;
    }

    //main
    public static void main(String[] args){

        int[][] input = new int[][] { {-1, 2, 3, -1, -1, -1},
                          {2, -1, -1, 5, 2, -1},
                          {3, -1, -1, -1, 5, -1},
                          {-1, 5, -1, -1, 1, 2},
                          {-1, 2, 5, 1, -1, 4},
                          {-1, -1, -1, 2, 4, -1},
                        };
                        //-1 represents an non-existant path

        System.out.println(Dijkstra(convert(input)));
    }
}

回答by Babar

The representation that you are calling 2D array, is the Adjacency matrix representation of a graph and the problem you are trying to solve is an instance of 'Single-Source Shortest Paths' problem. Dijkstra's algorithm is designed to solve this type of problem. This might be helpful http://renaud.waldura.com/doc/java/dijkstra/. Download the code from the site and read the documentation. Basically you will need to write code similar to following

您正在调用 2D 数组的表示是图形的邻接矩阵表示，您要解决的问题是“单源最短路径”问题的一个实例。Dijkstra 算法旨在解决此类问题。这可能会有所帮助http://renaud.waldura.com/doc/java/dijkstra/。从站点下载代码并阅读文档。基本上你需要编写类似于以下的代码

    RoutesMap map = map =  new DenseRoutesMap(5);
    map.addDirectRoute(City.A, City.B, 2);
    map.addDirectRoute(City.A, City.C, 3);
    map.addDirectRoute(City.B, City.A, 2);
    map.addDirectRoute(City.B, City.D, 5);
    map.addDirectRoute(City.B, City.D, 2);
    ...
    DijkstraEngine engine = new DijkstraEngine(map);
    int distance = engine.getShortestDistance(City.F);

回答by Paul Hinrichsen

Dont know if anyone is still interested in this matrix representation of Dijikstra but I have been thinking about coding Dijikstra in Actionscript and so first had to teach myself how Dijuikstra worked. Having done that and in trying to code it I realised only last night that I could represent the nodes and there distances in a matrix such as you have on top of this post. My theory is then that finding the shortest path will be a very simple matter. I am still experimenting to ensure that I correct.

不知道是否有人仍然对 Dijikstra 的这种矩阵表示感兴趣，但我一直在考虑在 Actionscript 中编码 Dijikstra，因此首先必须自学 Dijikstra 的工作原理。完成此操作并尝试对其进行编码后，我直到昨晚才意识到我可以表示矩阵中的节点和距离，例如您在这篇文章的顶部。我的理论是，找到最短路径将是一件非常简单的事情。我仍在试验以确保我是正确的。

In the matrix;

在矩阵中；

a b c d e z a - 2 3 - - - b 2 - - 5 2 - c 3 - - - 5 - d - 5 - - 1 2 e - 2 5 1 - 4 z - - - 2 4 -

abcdeza - 2 3 - - - b 2 - - 5 2 - c 3 - - - 5 - d - 5 - - 1 2 e - 2 5 1 - 4 z - - - 2 4 -

I start looking at row "a" (since this is the starting point) and pick the smallest number in the row being 2 (under b). So I write the path as "a - b" at a cost of 2. Then I go to the b row and again find the smallest number to the RIGHT of b (since we are already at the b node. This gives me 2 under the "e". So the path is now "a - b - e" at a total cost of 4. i Then look at the "e" row and the rule should be find the smallest number appearing after the "e" column. This would give me "z" and give the full path as "a - b - e - z" and a total cost of 8. However, and remember I only figured this out last night, the methodology needs to recognise that while looking at the "e" row another possibility is to go to the d column at a cost of 1. Then look at the d row for the lowest number after the d row which will give me the "z" row at a cost of 2.

我开始查看行“a”（因为这是起点）并选择行中的最小数字 2（在 b 下）。所以我将路径写为“a - b”，代价为 2。然后我去 b 行，再次找到 b 右边的最小数字（因为我们已经在 b 节点。这给了我 2 “e”。所以路径现在是“a - b - e”，总成本为 4。然后查看“e”行，规则应该是找到出现在“e”列之后的最小数字。这会给我“z”并将完整路径给出为“a - b - e - z”，总成本为 8。但是，请记住我昨晚才弄清楚这一点，该方法需要在查看时认识到这一点"e" 行另一种可能性是以 1 为代价转到 d 列。

Hence this is a better solution with the path being "a - b - e - d -z" at a total cost of 7 as you correctly said.

因此，这是一个更好的解决方案，路径为“a - b - e - d -z”，如您所说的那样，总成本为 7。

OK I still need to code this in Actionscript but my gut feeling is that it will be very easy to code in Actionscript. Afraid I have no experince in Java but if you agree with my method it should be easy to code in Java.

好的，我仍然需要在 Actionscript 中编写代码，但我的直觉是在 Actionscript 中编写代码非常容易。恐怕我没有 Java 经验，但如果您同意我的方法，那么用 Java 编码应该很容易。

Paul

保罗