这是分析图表的正确方法吗？

Question

大家好，我需要帮助分析图表，我已经实现了 Dijkstra 算法，但我不确定我的分析。这是分析图表的正确方法吗？

我的分析在评论里。

public class Dijkstra {

    for (int i = 0; i < distance.length; i++)//O(v^2)
    {
        visited[i] = 0; 
        preD[i] = 0;

        for (int j = 0; j < distance.length; j++)
        {
            matrix[i][j] = scan.nextInt(); 
            if (matrix[i][j]==0)
                matrix[i][j] = 999; 
        }
    }


    for (int counter = 0; counter < n; counter++)//O(V^2) 
    {
        min = 999;
        for (int i = 0; i < 3; i++)
        {
            if (min > distance[i] && visited[i]!=1) 
            {
                min = distance[i];
                nextNode = i;
            }
        } 




        for (int i = 0; i < n; i++)//O(E) 
        {
            if (visited[i]!=1)
            {
                if (min+matrix[nextNode][i] < distance[i])
                {
                    distance[i] = min+matrix[nextNode][i]; 
                    preD[i] = nextNode;
                }

            }

        }

    }//finally Dijkstra takes O(v^2) 
}

Answer 1

这是djikstra算法的经典实现，很容易注意到嵌套循环决定了复杂度。所以是的，你是对的。有一个更好的版本，使用优先数据结构来获取下一个最近的节点，复杂度下降到O(n * log n)。

这是分析图表的正确方法吗？

is this a correct way to analyze a graph?

java

algorithm

analysis

dijkstra