关于Dijkstra算法时间复杂度分析正确性的技术咨询

Hey there! Let's take a close look at your Dijkstra implementation and verify if your time complexity annotations are correct.

First, here's your code formatted clearly for reference:

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 k = 0; k < n; k++) {
            if (visited[k] == 0 && distance[k] < min) {
                min = distance[k];
                u = k;
            }
        }
        visited[u] = 1;
        // 更新邻接节点的最短路径
        for (int v = 0; v < n; v++) {
            if (visited[v] == 0 && matrix[u][v] + distance[u] < distance[v]) {
                distance[v] = matrix[u][v] + distance[u];
                preD[v] = u;
            }
        }
    }
}

你的时间复杂度分析完全合理，具体验证如下： #

• 第一部分初始化循环：外层循环执行v次（v为顶点总数，等于distance.length），内层循环同样执行v次，用于初始化邻接矩阵、访问标记数组和前驱节点数组。这部分的时间复杂度确实是O(v²)，你的标注准确。
• 第二部分核心算法循环：外层循环会执行v次（每个顶点都会被选中一次作为当前最短路径的起点）：
  • 每次循环中，寻找未访问的最小距离节点需要遍历所有v个顶点，时间开销为O(v)；
  • 更新所有邻接节点的最短路径同样需要遍历v个顶点，时间开销也为O(v)。
    单次外层循环的总开销是O(v)+O(v)=O(v)，执行v次后，这部分的总时间复杂度就是O(v²)，你的标注完全正确。

把两部分的时间复杂度相加，整个算法的总时间复杂度为O(v²)+O(v²)=O(v²)，这正是邻接矩阵实现的Dijkstra算法的标准时间复杂度，你的分析逻辑没有问题。

小补充：如果用优先队列（堆）优化寻找最小距离节点的步骤，算法时间复杂度可以降到O(E log v)（E为边数），但对于稠密图（边数接近v²），你当前这种邻接矩阵实现的O(v²)效率反而更优。

内容的提问来源于stack exchange，提问作者Thana Sa