java 使用邻接矩阵问题的 Dijkstra 算法

Dijkstra's Algorithm using Adjacency Matrix Issue

提问by JasonMortonNZ

'm trying to retrieve the shortest path between first and last node. The problem is my code always returns 0. I have a feeling this is because it's computing the distance between first node and first node, which is going to zero, but i'm not 100%. Why is my code always returning 0?

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

The adj matrix is [10][10] and all nodes are connected, and g.network[][] is the matrix.

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];
}

采纳答案by JasonMortonNZ

I think I may have solved the issue, by modifying the code as follows (I'm now passing in a start point instead of the hard-coded in "0"):

我想我可能已经解决了这个问题，通过如下修改代码（我现在传入一个起点而不是“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];
}

I ran this code through a for loop and voila....not just zero's being returned now.

我通过 for 循环运行了这段代码，瞧……现在不只是返回零。

回答by Ali

I read your code and I'm almost sure it's correct dijkstra algorithm so I think maybe you have a zero path between your first node and last node.

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