Graph Algorithm Complexity

Discrete Math · Axiom Academy

LESSON Graph Algorithm Complexity Understanding how graph algorithms scale and why representation matters for performance Before diving into specific algorithms, we need to understand what V and E represent: V (Vertices): The number of nodes in the graph E (Edges): The number of connections between nodes Relationship: In the worst case, E can be as large as V², which occurs in a complete graph where every vertex connects to every other vertex Depth-First Search and Breadth-First Search are foundational graph traversal algorithms with identical time complexity but different exploration strategies. Visit every vertex: Each of the V vertices is visited exactly once → O(V) Examine every edge: Each of the E edges is examined exactly once → O(E) Combined: Total operations = O(V + E) 3. Dijkstra's Algorithm: O(E log V) Dijkstra's algorithm finds the shortest path from a source vertex to all other vertices in a weighted graph with non-negative edge weights. Priority queue operations: Uses a min-heap to extract the vertex with minimum distance Each vertex: Extracted from the priority queue once → O(V log V) Each edge: May trigger a decrease-key operation in the priority queue → O(E log V) Dominant term: O(E log V) dominates when E > V Floyd-Warshall finds shortest paths between all pairs of vertices using dynamic programming. Unlike Dijkstra, it can handle negative edge weights. Three nested loops: For each intermediate vertex k, for each source i, for each destination j

This is the written version of the interactive lesson above. See the full Discrete Math course.