tczon
Back

Time Complexity of Graph Algorithms: BFS,DFS, Dijkstra, Floyd-Warshall

Last Updated: March 29, 2025
5 min
Time Complexity of Graph Algorithms: BFS,DFS, Dijkstra, Floyd-Warshall

Table of Content

When I first delved into the world of graph algorithms, I found myself navigating a labyrinth of techniques and complexities. It was a bit like trying to find my way through a maze without a map! Whether you're gearing up for a coding interview, looking to optimize a real-world application, or simply eager to understand the mechanics of efficient coding, grasping the time complexity of graph algorithms is crucial. In this guide, we’ll explore Breadth-First Search (BFS), Depth-First Search (DFS), Dijkstra's algorithm, and Floyd-Warshall. We’ll not only discuss the theory but also provide practical implementations that will help solidify these concepts.

Understanding Graph Representation: The Building Blocks

Before we dive into specific algorithms, it’s essential to understand how graphs are represented in code. This representation directly affects the time complexity of our algorithms.

Adjacency Matrix

An adjacency matrix is a square grid where each cell indicates whether there is an edge between two vertices. This method is straightforward but can consume a lot of memory.

// Adjacency matrix implementation
#include <iostream>
using namespace std;
 
int main() {
    int n = 5; // Number of vertices
    int m = 7; // Number of edges
 
    // Create an adjacency matrix
    int adj[n+1][n+1] = {0}; // Initialize with zeros
 
    // Add edges (for an undirected graph)
    for(int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        adj[u][v] = 1;
        adj[v][u] = 1; // Remove this line for directed graphs
    }
 
    return 0;
}

The space complexity here is O(n²), which can become quite large as the number of vertices increases. This representation works well for dense graphs where most vertices are interconnected.

Adjacency List

For many applications, an adjacency list is more efficient. Each vertex has a list containing its adjacent neighbors:

// Adjacency list implementation
#include <vector>
#include <iostream>
using namespace std;
 
int main() {
    int n = 5; // Number of vertices
    int m = 7; // Number of edges
 
    // Create an adjacency list
    vector<int> adj[n+1];
 
    // Add edges (for an undirected graph)
    for(int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u); // Remove this line for directed graphs
    }
 
    return 0;
}

The space complexity here is O(V + E), making this representation ideal for sparse graphs where E (edges) is much smaller than V² (the maximum possible edges).

Analyze Time & Space Complexity: Try our Code Analyzer Tool for free 👆🏻

Optimize your Code: Try our Code Optimizer Tool for free 👆🏻

Breadth-First Search (BFS): A Level-Order Approach

BFS explores the graph level by level, ensuring that all nodes at the current distance from the source are examined before moving deeper.

How Breadth-First Search (BFS) Operates

  1. Start at a source node and mark it as visited.
  2. Explore all unvisited neighbors before moving to the next level.
  3. Use a queue to track nodes that need to be visited next.

Time Complexity Analysis of Breadth-First Search (BFS)

The time complexity of BFS is O(V + E), where V represents the number of vertices and E represents the number of edges. This is because:

  • Each vertex is processed once: O(V)
  • Each edge is examined once: O(E)

The space complexity is also O(V), as the queue may need to store all vertices at the current level before proceeding to the next.

Implementation of Breadth-First Search (BFS)

#include <queue>
#include <iostream>
#include <vector>
#include <map>
#include <set>
using namespace std;
 
class Graph {
public:
    Graph() {}
 
    void addEdge(int u, int v) {
        adjList[u].insert(v);
        adjList[v].insert(u); // For undirected graph
    }
 
    const map<int, set<int>>& getAdjList() const {
        return adjList;
    }
private:
    map<int, set<int>> adjList;
};
 
vector<int> bfs(const Graph& graph, int start) {
    set<int> visited;
    queue<int> queue;
    vector<int> result;
 
    queue.push(start);
 
    while (!queue.empty()) {
        int node = queue.front();
        queue.pop();
 
        if (visited.find(node) == visited.end()) {
            visited.insert(node);
            result.push_back(node);
 
            for (int neighbor : graph.getAdjList().at(node)) {
                if (visited.find(neighbor) == visited.end()) {
                    queue.push(neighbor);
                }
            }
        }
    }
 
    return result;
}
 
int main() {
    Graph graph;
    graph.addEdge(0, 1);
    graph.addEdge(0, 2);
    graph.addEdge(1, 3);
    graph.addEdge(1, 4);
    graph.addEdge(2, 5);
 
    vector<int> traversal = bfs(graph, 0);
    cout << "BFS traversal: ";
    for (int node : traversal) {
        cout << node << " ";
    }
    // Output: 0 1 2 3 4 5
    return 0;
}

This implementation highlights how BFS systematically explores a graph level by level.

When to Use Breadth-First Search (BFS)

BFS shines when:

  • You need to find the shortest path in an unweighted graph.
  • You want to explore all nodes at a certain distance from the source.
  • The solution is likely close to the starting point.

Depth-First Search (DFS): Going Deep Before Wide

In contrast to BFS, DFS dives deep into one branch before backtracking to explore other paths—think of it as following one route in a maze until you hit a dead end.

How Depth-First Search (DFS) Works

  1. Start at a source node and mark it as visited.
  2. Recursively explore each unvisited neighbor.
  3. Backtrack when there are no unvisited neighbors left.

Time Complexity Analysis of Depth-First Search (DFS)

The time complexity for DFS is also O(V + E):

  • Each vertex is processed once: O(V)
  • Each edge is examined once: O(E)

The space complexity can reach O(V) in the worst case due to the recursion stack storing the entire path from root to leaf.

Implementation of Depth-First Search (DFS)

#include <iostream>
#include <vector>
#include <set>
#include <map>
using namespace std;
 
class Graph {
public:
    Graph() {}
 
    void addEdge(int u, int v) {
        adjList[u].insert(v);
        adjList[v].insert(u); // For undirected graph
    }
 
    const map<int, set<int>>& getAdjList() const {
        return adjList;
    }
private:
    map<int, set<int>> adjList;
};
 
void dfsUtil(const Graph& graph, int node, set<int>& visited, vector<int>& result) {
    visited.insert(node);
    result.push_back(node);
 
    for (int neighbor : graph.getAdjList().at(node)) {
        if (visited.find(neighbor) == visited.end()) {
            dfsUtil(graph, neighbor, visited, result);
        }
    }
}
 
vector<int> dfs(const Graph& graph, int start) {
    set<int> visited;
    vector<int> result;
 
    dfsUtil(graph, start, visited, result);
 
    return result;
}
 
int main() {
    Graph graph;
    graph.addEdge(0, 1);
    graph.addEdge(0, 2);
    graph.addEdge(1, 3);
    graph.addEdge(1, 4);
    graph.addEdge(2, 5);
 
    vector<int> traversal = dfs(graph, 0);
    cout << "DFS traversal: ";
    for (int node : traversal) {
        cout << node << " ";
    }
 
   return 0;
}

DFS can be implemented using either recursion or an explicit stack structure. It allows for deep exploration before backtracking.

When to Use Depth-First Search (DFS)

DFS excels when:

  • You need to explore all possible paths in a graph.
  • The solution might be buried deep within.
  • You're checking for connectedness or cycle detection.
  • You need topological sorting or other advanced operations.

Comparing Breadth-First Search (BFS) and Depth-First Search (DFS)

While both BFS and DFS share similar time complexities—O(V + E)—they behave quite differently in practice.

Opt for Breadth-First Search (BFS) when:

  • You require the shortest path in an unweighted scenario.
  • The solution isn’t far from your starting point.
  • You’re dealing with wide and shallow graphs.

Opt for Depth-First Search (DFS) when:

  • You want to explore every possible path.
  • The solution may lie deep within the structure.
  • Memory usage is a concern since DFS typically requires less memory than BFS in wide graphs.

If you’re trying to find the shortest route or need to examine all nodes at equal depth first—BFS usually wins out. Conversely, if you’re exploring paths or dealing with memory constraints—DFS may be your best bet.

Dijkstra's Algorithm: Shortest Paths in Weighted Graphs

While BFS finds paths based solely on edge count, Dijkstra's algorithm identifies the shortest paths in weighted graphs where edges have varying costs.

How Dijkstra's Algorithm Functions

  1. Initialize distances: set your source node distance to zero and all others to infinity.
  2. Use a priority queue to select the node with the smallest tentative distance.
  3. Explore its neighbors and update their distances if you find a shorter path.
  4. Mark that node as processed.
  5. Repeat until all nodes are processed.

Time Complexity Analysis of Dijkstra's Algorithm

The time complexity can vary based on implementation:

  • Using a binary heap yields O(E log V).
  • With Fibonacci heaps: O(E + V log V).
  • Using an array results in O(V²) (better suited for dense graphs).

The space complexity stands at O(V) due to storing distances and managing the priority queue.

Implementation of Dijkstra's Algorithm

#include <iostream>
#include <vector>
#include <queue>
#include <limits>
using namespace std;
 
typedef pair<int, int> pii; // Pair representing (distance, vertex)
 
vector<int> dijkstra(vector<vector<pii>>& graph, int start) {
   int n = graph.size();
   vector<int> dist(n, numeric_limits<int>::max());
   dist[start] = 0;
 
   priority_queue<pii, vector<pii>, greater<pii>> pq; // Min-heap priority queue
   pq.push({0, start});
 
   while (!pq.empty()) {
       int u = pq.top().second;
       int d = pq.top().first;
       pq.pop();
 
       if (d > dist[u]) continue;
 
       for (auto& edge : graph[u]) {
           int v = edge.first;
           int weight = edge.second;
 
           if (dist[u] + weight < dist[v]) {
               dist[v] = dist[u] + weight;
               pq.push({dist[v], v});
           }
       }
   }
 
   return dist;
}
 
int main() {
   int n = 5; // Number of vertices
   vector<vector<pii>> graph(n);
 
   // Add edges (vertex and weight)
   graph[0].push_back({1, 2});
   graph[0].push_back({2, 4});
   graph[1].push_back({2, 1});
   graph[1].push_back({3, 7});
   graph[2].push_back({4, 3});
   graph[3].push_back({4, 1});
 
   vector<int> distances = dijkstra(graph, 0);
 
   cout << "Shortest distances from vertex 0:" << endl;
   for (int i = 0; i < n; i++) {
       cout << "To vertex " << i << ": " << distances[i] << endl;
   }
 
   return 0;
}

Dijkstra's algorithm proves invaluable for finding shortest paths in weighted graphs with non-negative edge weights—widely applied in network routing protocols and GPS navigation systems.

Floyd-Warshall Algorithm: All-Pairs Shortest Paths Made Simple

Whereas Dijkstra finds paths from one source vertex to others individually, Floyd-Warshall computes shortest paths between all pairs of vertices simultaneously.

How Floyd-Warshall Operates

This algorithm employs dynamic programming:

  1. Initialize a distance matrix with direct edge weights.
  2. For each vertex k considered as an intermediate point,
  3. For every pair of vertices (i,j), check if passing through k offers a shorter route,
  4. Update accordingly if it does.

Time Complexity Analysis of Floyd-Warshall

The time complexity stands at O(V³), given three nested loops running V times each. While this might seem less efficient than running Dijkstra V times (which would yield O(V * E log V)), Floyd-Warshall can outperform it on dense graphs due to its simpler structure and better cache performance.

Space Complexity Considerations

The space complexity here is O(V²), required for maintaining the distance matrix.

Implementation of Floyd-Warshall Algorithm

#include <iostream>
#include <vector>
#include <limits>
using namespace std;
 
void floydWarshall(vector<vector<int>>& graph) {
   int n = graph.size();
 
   vector<vector<int>> dist = graph;
 
   for (int k = 0; k < n; k++) {
       for (int i = 0; i < n; i++) {
           for (int j = 0; j < n; j++) {
               if (dist[i][k] == numeric_limits<int>::max() ||
                   dist[k][j] == numeric_limits<int>::max())
                   continue;
 
               int through_k = dist[i][k] + dist[k][j];
               if (through_k < dist[i][j])
                   dist[i][j] = through_k;
           }
       }
   }
 
   cout << "All-pairs shortest paths:" << endl;
   for (int i = 0; i < n; i++) {
       for (int j = 0; j < n; j++) {
           if (dist[i][j] == numeric_limits<int>::max())
               cout << "INF ";
           else
               cout << dist[i][j] << " ";
       }
       cout << endl;
   }
}
 
int main() {
   int n = 4;
   vector<vector<int>> graph(n,
     vector<int>(n,
     numeric_limits<int>::max()));
 
   for (int i = 0; i < n; i++)
       graph[i][i] = 0;
 
   // Add edges
   graph[0][1] = 5;
   graph[0][3] = 10;
   graph[1][2] = 3;
   graph[2][3] = 1;
 
   floydWarshall(graph);
 
   return 0;
}

Floyd-Warshall stands out as one of those rare algorithms that performs better on adjacency matrices compared to adjacency lists due to its tight loops and simplicity.

Comparing Shortest Path Algorithms: Navigating Choices Between Dijkstra and Floyd-Warshall

Both Dijkstra’s algorithm and Floyd-Warshall tackle shortest path problems but shine under different circumstances:

Dijkstra’s Algorithm:

  • Time Complexity: O(E log V) with binary heaps.
  • Best For: Single-source shortest paths.
  • Limitations: Cannot handle negative edge weights effectively.
  • Efficiency: More suitable for sparse graphs.

Floyd-Warshall Algorithm:

  • Time Complexity: O(V³).
  • Best For: All-pairs shortest paths.
  • Capabilities: Can handle negative edge weights but not negative cycles.
  • Efficiency: More effective on dense graphs due to its straightforward approach and better cache locality.

In practical scenarios where you need paths from one vertex to many others quickly—Dijkstra often takes precedence. If you're after all-pairs shortest paths or dealing with negative weights—Floyd-Warshall may be your go-to option.

Advanced Topics Worth Exploring Beyond Basics

While we’ve covered essential algorithms here are some additional ones that deserve mention:

Bellman-Ford Algorithm

  • Time Complexity: O(V · E).
  • Strengths: Capable of handling negative edge weights and detecting negative cycles effectively.

PageRank Algorithm

  • Usage: Ranks web pages based on their importance through link analysis.
  • Complexity: Depends on convergence criteria along with nodes/edges involved—often requiring iterative methods over multiple rounds until stability occurs.

Minimum Spanning Tree Algorithms like Kruskal’s and Prim’s

Both have time complexities around O(E log V) and are used primarily for finding minimum spanning trees efficiently across various applications including network design problems.

Optimizing Graph Algorithms in Real-Life Scenarios

Understanding theory is crucial but optimizing algorithms practically often requires additional considerations:

Choosing Data Structures Wisely

  1. Adjacency Matrix vs Adjacency List: An adjacency matrix works well with dense graphs while adjacency lists are better suited for sparse ones.
  2. Priority Queue Implementation: In Dijkstra’s algorithm using binary heaps tends towards faster performance due largely due simplicity alongside cache efficiency benefits over alternatives like Fibonacci heaps which may offer theoretical advantages but introduce overheads during implementation phases too often leading back towards simpler structures instead!
  3. Set vs Array Usage: Using boolean arrays instead tracking visited nodes via sets can lead towards faster execution times especially within fixed vertex counts present across many common scenarios encountered regularly today!

Modifying Algorithms

  1. Bidirectional Search Techniques: When searching paths consider exploring both source/destination simultaneously—it can drastically reduce search spaces involved leading towards quicker results overall!
  2. Early Termination Strategies: If only needing one path towards specific target node consider stopping once found rather than continuing exploration unnecessarily wasting resources!
  3. Parallelization Opportunities: Many algorithms lend themselves well towards parallelization strategies leveraging multi-core processors available today!

Conclusion: Making Informed Choices About Algorithms

Understanding these various complexities associated with different algorithms will empower you immensely when tackling problems head-on! Here’s quick recap:

  • BFS: O(V + E)—Ideal when searching unweighted shortest routes or exploring levels systematically!
  • DFS: O(V + E)—Best suited exploring every possible route deeply while checking connectivity/cycles!
  • Dijkstra’s Algorithm: O(E log V)—Most effective single-source shortest path solutions within weighted contexts!
  • Floyd-Warshall Algorithm: O(V³)—Perfectly positioned finding all-pairs shortest pathways especially within denser structures!

When selecting an algorithm keep these factors in mind:

  1. What specific problem do you need solving?
  2. What characteristics define your particular input data?
  3. Are there any constraints regarding memory usage?
  4. Do you require single-source versus all-pairs solutions?

In closing remember that while theoretical complexities matter practical considerations such as cache efficiency also play vital roles influencing overall performance outcomes significantly! With this knowledge under your belt—you’re now equipped ready tackle challenging tasks confidently whether they arise during interviews or real-world projects alike! Happy coding! 🚀

Try our Code Analyzer Tool for free 👆🏻

Try our Code Optimizer Tool for free 👆🏻

Ads