为什么使用矩阵表示的 Dijkstra 算法的时间复杂度比稠密图的列表表示更好

Question

我一直在互联网上查找，但到目前为止，我还没有找到我的问题的答案。

对于使用矩阵表示的 Dijkstra 算法，时间复杂度为 O(V^2)。

但是对于列表表示，时间复杂度为 O((V+E)Log(V))。

但是，当我绘制各种顶点和边密度的图时，我发现矩阵表示实际上对于更密集的图更好。 **但为什么 ？因为理论上来说 O(V^2) 应该做得最差。 **

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)] # adjacency matrix
        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
                    else:
                        self.matrix[i][j] = 0

        # Print the number of vertices and edges
        if printLog:
            print("Vertices:", self.vertices)
            print("Edges:", self.edges)
            print("Edge Density:", round(self.calculate_edge_density(),5))

def dijkstraM(self, source, printLog = True):
        # Uses an array as priority queue

        numOfVertex = 0
        numOfEdges = 0
        
        d = [float('inf') for i in range(self.vertices)]
        pi = [float('inf') for i in range(self.vertices)] # Predecessor so pi[i] = j means j is the predecessor of i
        s = [False for i in range(self.vertices)] # If S[i] = True, then the vertex i is in the set S, else not
        pq = [float('inf') for i in range(self.vertices)]

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

    
        # While the priority queue is not empty equivalent
        while True:
            u = self.__extractCheapest__(pq)

            # If the priority queue is empty, then break 
            # Means that all the vertices have been added to the set S
            if u == -1:
                break

            s[u] = True # Add the vertex u to the set S

            numOfVertex += 1
            
            for v in range(self.vertices): #(O(|V|) because we are iterating through all the vertices)
                numOfEdges += 1

                # Check if the edge u->v exists and if v is not in the set S 
                # And if the distance from source to v is greater than the distance from source to u + the weight of the edge u->v
                if self.matrix[u][v] != 0 and s[v] == False and ((d[u] + self.matrix[u][v]) < d[v]):

                    # Update the distance from source to v
                    d[v] = d[u] + self.matrix[u][v]
                    # Update the predecessor of v
                    pi[v] = u
                    # Update the priority queue (O(1)) because we are inserting
                    pq[v] = d[v]
                    

    def dijkstraL(self, source, printLog = True):
        # Uses minimizing heap as priority queue
        
        numOfVertex = 0
        numOfEdges = 0
        
        d = [float('inf') for i in range(self.vertices)]
        pi = [float('inf') for i in range(self.vertices)] # Predecessor so pi[i] = j means j is the predecessor of i
        s = [False for i in range(self.vertices)] # If S[i] = True, then the vertex i is in the set S, else not

        ########### IMPLEMENTATION IS ROUGHLY THE SAME AS THE MATRIX IMPLMENTATION ###########
        # Just that the extraction Cheapest and the update priority queue is different

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

        pq = PriorityQueue()
        pq.insert((0, source)) # Insert the vertex, distance O(lg|v|)  because heappq looks sees the first elemnt in the tuple as the priority

        # Only need to fixHeap everytime we insert instead of heapifying it since we are only one element at a time
        while not pq.is_empty(): # While the priority queue is not empty equivalent
         
            dist, u = self.__extractCheapestPQ__(pq) # Extract the cheapest vertex from the priority queue (O(1))

            s[u] = True # Add the vertex u to the set S

            numOfVertex += 1

            for v in self.adj_list[u]: # (O(|E|) because we are iterating through all the edges connected to u)
                numOfEdges += 1

                # Check if v is not in the set S
                # And if the distance from source to v is greater than the distance from source to u + the weight of the edge u->v
                if s[v[0]] == False and ((dist + v[1]) < d[v[0]]):
                    # Update the distance from source to v
                    d[v[0]] = dist + v[1]
                    # Update the predecessor of v
                    pi[v[0]] = u
                    # Update the priority queue (O(lg|v|)) because we are inserting
                    pq.insert((d[v[0]], v[0]))


    def __extractCheapestPQ__(self, pq):

        eC = pq.remove()

        return eC
    
    def __extractCheapest__(self, pq):
        min = float('inf')
        u = 0

        # print("PQ" , pq) 

        # Find the minimum in the priority queue O(|V|))
        for i in range(self.vertices):
            if pq[i] < min:
                min = pq[i]
                u = i

        # Remove the minimum from the priority queue because it is now in the set S
        pq[u] = float('inf')

        # If the minimum is still infinity, then the priority queue is empty
        if min == float('inf'):
            return -1

        return u

这是我生成的图表

谢谢你。

Answer 1

通过提供时间复杂度，您几乎已经回答了自己的问题：

• 矩阵：O(𝑉²)
• 列表：O((𝑉+𝐸)log𝑉)

只有邻接表算法的复杂度取决于边的数量，因此预计在您的统计中您会发现第一个算法在增加边数时没有显示出太大的差异，而对于第二个算法来说，这有效果。

请注意，对于最大边缘密度，我们有 𝐸 = O(𝑉²)，这使得第二个复杂度为 O(𝑉²log𝑉)，而不是 O(𝑉²)！

对于给定的 𝑉 值，是否存在矩阵算法比其他算法运行“更快”的密度，仅从复杂性无法看出 - 这取决于实现和架构提供的常数和系数，但我们可以确信，当 𝑉 足够大时，存在一个密度，高于该密度矩阵算法将运行得更快。