Shortest Path Algorithms (Dijkstra, Bellman-Ford)

📘 Data Structure and Algorithm 👁 132 views 📅 Nov 05, 2025

⏱ Estimated reading time: 2 min

Shortest Path Algorithms (Dijkstra and Bellman-Ford)

The shortest path problem finds the path between two vertices that minimizes the total edge weight. Two popular algorithms for this are Dijkstra’s Algorithm and Bellman-Ford Algorithm.

1. Dijkstra’s Algorithm

Dijkstra’s algorithm finds the shortest path from a source vertex to all other vertices in a weighted graph with non-negative edges.

// Example: Dijkstra’s Algorithm (C++)
void dijkstra(int V, vector>>& adj, int src) {
    vector dist(V, INT_MAX);
    priority_queue, vector>, greater>> pq;
    dist[src] = 0;
    pq.push({0, src});

    while (!pq.empty()) {
        int u = pq.top().second;
        pq.pop();
        for (auto it : adj[u]) {
            int v = it.first;
            int weight = it.second;
            if (dist[u] + weight < dist[v]) {
                dist[v] = dist[u] + weight;
                pq.push({dist[v], v});
            }
        }
    }
}

Time Complexity:

O((V + E) log V) using a priority queue.

2. Bellman-Ford Algorithm

Bellman-Ford can handle graphs with negative edge weights. It relaxes all edges (V−1) times to find the shortest path.

// Example: Bellman-Ford Algorithm (C++)
void bellmanFord(int V, vector>& edges, int src) {
    vector dist(V, INT_MAX);
    dist[src] = 0;
    for (int i = 0; i < V - 1; i++) {
        for (auto e : edges) {
            int u = e[0], v = e[1], w = e[2];
            if (dist[u] != INT_MAX && dist[u] + w < dist[v])
                dist[v] = dist[u] + w;
        }
    }
}

Time Complexity:

O(V * E)

Comparison

Algorithm	Handles Negative Weights	Time Complexity
Dijkstra	No	O((V + E) log V)
Bellman-Ford	Yes	O(V * E)

Applications

GPS and navigation systems
Network routing protocols
Optimal path finding in weighted graphs

Conclusion

Both Dijkstra and Bellman-Ford algorithms are essential for solving shortest path problems. Dijkstra’s is faster for non-negative graphs, while Bellman-Ford is versatile and can detect negative cycles.

🔒 Some advanced sections are available for Registered Members
Register Now

← Previous