Java中的二维数组Dijkstra算法

Question

这是一个学校项目；我遇到了很多麻烦，而且似乎找不到易懂的解决方案。

   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 -

那是一个二维数组。所以如果你想找到最短的路径，从a、b、e、d、z=7和(a,b)=(b,a)开始——它会带你到新的行来寻找该行相邻的路径。

有人能帮我实现Dijkstra算法吗？我真的很感激。(我似乎更喜欢使用数组，映射和集合让我有点困惑，列表是可以管理的——虽然我愿意研究任何解决方案)

[至少我不只是从网上抄袭源代码。我真的想学这些东西......只是真的很难(>_<)]

哦，起点是A，终点是Z

像大多数人一样，我并不觉得算法的概念难——我只是无法正确编写代码......请帮帮我？

示例代码——一个朋友帮了我很多忙(虽然它充满了我难以理解的数据结构)，我还试图将从dreamincode.net/forums/blog/martyr2/index.php?showentry=578的C++代码改编成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)));
    }
}

- Stan

Answer 1

你所说的二维数组表示法是图的邻接矩阵表示法，而你要解决的问题是“单源最短路径”问题的一个实例。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);

- Babar

---

不幸的是，那个网站对我帮助不大。它没有处理我需要的二维数组的功能...还有其他人有解决方案/建议吗？ - Stan

@Babar：很好的引导他朝着正确的方向前进，而不泄露所有的细节。+1 - William Brendel

非常好的TA式回答 :) +1。 - Jared

@Stan - Babar鼓励你考虑实现算法，而不是数据结构。这绝对是学习解决方案的更好方法。 - Jared

谢谢大家--我一定会尽快研究阅读和实现...虽然这主要是下周的事情--这周我很忙。我有机会/时间时会回复的;)!! - Stan

Answer 2

不知道还有没有人对这个Dijikstra的矩阵表示感兴趣，但我一直在思考如何使用Actionscript编码Dijikstra，所以首先必须教自己如何运作Dijuikstra。在完成了这些工作并尝试编码时，我意识到昨晚我可以用像您在此帖子顶部展示的矩阵来表示节点和距离。我的理论是，找到最短路径将是非常简单的事情。我仍在实验中以确保我是正确的。

在矩阵中：

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 -

我开始查看行“a”（因为这是起点），并选择该行中最小的数字，即“b”下面的2。因此，我将路径写为“a-b”，成本为2。然后我转到b行，并再次找到右侧最小的数字（因为我们已经在b节点）。这使我在“e”下方得到了2。因此，路径现在是“a-b-e”，总成本为4。然后查看“e”行，规则应该是查找出现在“e”列之后的最小数字。这会给我“z”，并给出完整路径为“a-b-e-z”，总成本为8。但是，需要注意的是，当查看“e”行时，另一个可能性是以1的成本转到d列。然后查看d行，找到d行之后的最低数字，这将以2的成本给我“z”行。

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

好的，我仍然需要在Actionscript中编写这段代码，但我的直觉告诉我，在Actionscript中编写它将非常容易。很抱歉我没有Java方面的经验，但如果您同意我的方法，那么在Java中编写它应该也很容易。

保罗

- Paul Hinrichsen