为何稠密图中邻接矩阵实现的Dijkstra算法性能更优？

我查了很多资料还是没搞懂：邻接矩阵实现的Dijkstra时间复杂度是O(V²)，邻接表实现的是O((V+E)logV)，但测试不同顶点数、边密度的图后发现，稠密图里矩阵实现的性能反而更好。理论上O(V²)应该更差才对，这是为什么？

我的实现代码 #

import random

class Graph:
    def generateRandomGraph(self, vertices, chancesToSpawnEdge = 0.5, printLog = True):
        self.edges = 0
        self.vertices = vertices
        self.matrix = [[float('inf') for i in range(vertices)] for j in range(vertices)] # 邻接矩阵
        self.adj_list = {}
        self.type = "ADJ_MATRIX"
        for i in range(vertices):
            for j in range(vertices):
                if random.choices([0, 1], weights=[(1-chancesToSpawnEdge), chancesToSpawnEdge])[0]:
                    if i != j:
                        self.matrix[i][j] = random.randint(1, 100)
                        self.edges += 1
                        # 原代码未填充邻接表，此处补充修复
                        if i not in self.adj_list:
                            self.adj_list[i] = []
                        self.adj_list[i].append( (j, self.matrix[i][j]) )
                    else:
                        self.matrix[i][j] = 0

        # 输出顶点、边数和边密度
        if printLog:
            print("Vertices:", self.vertices)
            print("Edges:", self.edges)
            print("Edge Density:", round(self.calculate_edge_density(),5))

    def calculate_edge_density(self):
        # 补充边密度计算逻辑
        max_edges = self.vertices * (self.vertices - 1)
        return self.edges / max_edges if max_edges > 0 else 0

    def dijkstraM(self, source, printLog = True):
        # 用数组模拟优先队列的邻接矩阵版本
        numOfVertex = 0
        numOfEdges = 0
        
        d = [float('inf') for _ in range(self.vertices)]
        pi = [float('inf') for _ in range(self.vertices)] # 前驱节点数组
        s = [False for _ in range(self.vertices)] # 标记是否已处理
        pq = [float('inf') for _ in range(self.vertices)]

        s[source] = True
        d[source] = 0
        pq[source] = 0

        # 模拟优先队列非空的循环
        while True:
            u = self.__extractCheapest__(pq)
            if u == -1:
                break

            s[u] = True
            numOfVertex += 1
            
            for v in range(self.vertices):
                numOfEdges += 1
                # 检查边存在、未处理且距离可更新
                if self.matrix[u][v] != float('inf') and not s[v] and (d[u] + self.matrix[u][v] < d[v]):
                    d[v] = d[u] + self.matrix[u][v]
                    pi[v] = u
                    pq[v] = d[v]

    def dijkstraL(self, source, printLog = True):
        # 用最小堆做优先队列的邻接表版本
        import heapq
        
        numOfVertex = 0
        numOfEdges = 0
        
        d = [float('inf') for _ in range(self.vertices)]
        pi = [float('inf') for _ in range(self.vertices)]
        s = [False for _ in range(self.vertices)]

        d[source] = 0
        pq = []
        heapq.heappush(pq, (0, source))

        while pq:
            dist, u = heapq.heappop(pq)
            # 延迟删除：跳过已处理的冗余节点
            if s[u]:
                continue
            s[u] = True
            numOfVertex += 1

            if u not in self.adj_list:
                continue
            for v, weight in self.adj_list[u]:
                numOfEdges += 1
                if not s[v] and (d[u] + weight < d[v]):
                    d[v] = d[u] + weight
                    pi[v] = u
                    heapq.heappush(pq, (d[v], v))

    def __extractCheapest__(self, pq):
        min_val = float('inf')
        u = -1
        # 线性扫描找最小值
        for i in range(self.vertices):
            if pq[i] < min_val:
                min_val = pq[i]
                u = i
        if u != -1:
            pq[u] = float('inf')
        return u if min_val != float('inf') else -1

测试结果图 #

问题解答 #

1. 你搞反了理论复杂度的结论 #

对于稠密图，边数E≈V²（几乎每对顶点都有边），此时邻接表实现的时间复杂度O((V+E)logV)≈O(V²logV)，这明显高于邻接矩阵的O(V²)。理论上，矩阵实现本来就应该在稠密图中表现更好，你的测试结果其实是符合理论的，之前的认知有误。

2. 原邻接表实现存在致命缺陷 #

看你贴的代码，generateRandomGraph方法只构建了邻接矩阵，完全没有往self.adj_list中添加任何边数据。这会导致dijkstraL中的遍历边循环根本不执行，算法相当于没有处理任何边，测试结果自然不真实。这是导致你困惑的核心实现错误。

3. 缓存友好性的实际影响 #

邻接矩阵是连续的二维数组，CPU缓存命中率远高于邻接表（邻接表是分散的字典/链表结构，内存地址不连续）。在稠密图中，矩阵的连续内存访问能充分利用CPU的多级缓存，实际运行速度会比理论复杂度的预测更快；而邻接表的分散访问会频繁触发缓存 miss，拖慢执行效率。

4. 优先队列的常数因子差异 #

• 矩阵版本用数组模拟优先队列，线性扫描找最小值的常数因子极小，只是简单的数组遍历和比较。
• 邻接表版本的堆操作（即使是标准库的heapq），每次heappush和heappop都涉及堆调整，常数因子远大于线性扫描。在稠密图中，V²次操作下，堆操作的累计开销会显著高于线性扫描。

优化建议 #

• 先修复邻接表的构建逻辑，确保generateRandomGraph同步填充邻接表（如上面代码中补充的部分）。
• 使用Python标准库的heapq实现优先队列，并加入「延迟删除」逻辑（跳过已处理的顶点），避免重复入队的冗余开销。
• 重新测试后，你会发现：稠密图中矩阵版本依然有优势，但邻接表版本的性能会接近理论预期，而不是之前的异常情况。

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