这是分析图形的正确方法

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)。