Dijkstra算法使用邻接矩阵问题

Question

我正在尝试检索第一个节点和最后一个节点之间的最短路径。问题是我的代码总是返回0。我有一种感觉，这是因为它正在计算第一个节点和第一个节点之间的距离，这将变成零，但我不确定。为什么我的代码总是返回0？

邻接矩阵是[10][10]，所有节点都连接在一起，g.network[][]是该矩阵。

private static int dijkstras(Graph g) {
    // Dijkstra's Algorithm
    int[] best = new int[g.network.length];
    boolean[] visited = new boolean[g.network.length];
    int max = 10000; // Infinity equivalent.
    for (int i = 0; i < g.network.length; i++)
    {
        best[i] = max;
        visited[i] = false;
    }

    best[0] = 0;

    for(int i = 0; i < g.network.length; i++)
    {
        int min = max;
        int currentNode = 0;
        for (int j = 0; j < g.network.length; j++)
        {
            if (!visited[j] && best[j] < min)
            {
                currentNode = j;
                min = best[j];
            }
        }
        visited[currentNode] = true;
        for (int j = 0; j < g.network.length; j++)
        {
            if (g.network[currentNode][j] < max && best[currentNode] + g.network[currentNode][j] < best[j])
            {
                best[j] = best[currentNode] + g.network[currentNode][j];
            }
        }
    }
            return best[g.network.length - 2];
}

- JasonMortonNZ

---

看起来你少了一些代码，也许是结束方法的 return 0;？当然我只是开玩笑啦，但我确实没有看到任何返回语句 :-/ - Jeremy

除了缺少返回语句，以至于它实际上无法编译之外，你的代码没有使用start参数，因此它不可能将起点与任何其他节点区分开。这意味着在某个时候你将开始与开始进行比较，如果你返回任何东西，那么它可能是最小距离为0。 - Don Roby

抱歉，当我复制并粘贴我的代码时，我错过了返回语句。在之前的尝试中，我调用方法时使用了“start”，但尚未删除它。现在我将这样做，因为它是多余的。顺便说一下，“start”在之前的尝试中被设置为0。 - JasonMortonNZ

Dijkstra算法没有起始顶点是无法运行的。 - Louis Wasserman

我知道，但是与其将起始节点索引传递到方法中，不如在我的代码中从零开始。 - JasonMortonNZ

提供一个失败的单元测试会很有用。 - Rob Kielty

Answer 1

我认为我可能解决了这个问题，通过修改代码如下（现在传入一个起点而不是硬编码的“0”）：

    private static int dijkstras(Graph g, int start) // Added a start point.
    {
    // Dijkstra's Algorithm
    int[] best = new int[g.network.length];
    boolean[] visited = new boolean[g.network.length];
    int max = 10000; // Infinity equivalent.
    for (int i = 0; i < g.network.length; i++)
    {
        best[i] = max;
        visited[i] = false;
    }

    best[start] = start; // Changed the 0 to variable start.

    for(int i = 0; i < g.network.length; i++)
    {
        int min = max;
        int currentNode = 0;
        for (int j = 0; j < g.network.length; j++)
        {
            if (!visited[j] && best[j] < min)
            {
                currentNode = j;
                min = best[j];
            }
        }
        visited[currentNode] = true;
        for (int j = 0; j < g.network.length; j++)
        {
            if (g.network[currentNode][j] < max && best[currentNode] +   g.network[currentNode][j] < best[j])
            {
                best[j] = best[currentNode] + g.network[currentNode][j];
            }
        }
    }
            return best[g.network.length - 2];
}

我通过一个for循环运行了这段代码，然后......现在不仅返回零了。

- JasonMortonNZ

Answer 2

我看了你的代码，几乎确定它是正确的Dijkstra算法，所以我认为可能你的第一个节点和最后一个节点之间没有路径。

- Ali

---

我无法回答自己的问题，因为声望太低，但我已经在这里粘贴了我的解决方法。你是对的，因为我设置了best [0] = 0，它总是返回零，因为它是节点之间的零路径。 http://pastebin.com/nmp8P1zW - JasonMortonNZ