3

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

adj矩阵为[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];
}
4

2 回答 2

3

我想我可能已经解决了这个问题，通过如下修改代码（我现在传入一个起点而不是硬编码在“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 循环运行这段代码，瞧……现在不只是返回零。

于 2012-05-03T23:11:53.223 回答
1

我阅读了您的代码，并且几乎可以确定它是正确的 dijkstra 算法，所以我认为您的第一个节点和最后一个节点之间的路径可能为零。

于 2012-05-03T02:56:17.087 回答