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
🚀 Want to Test Your Knowledge?
Take quizzes related to this topic and see where you stand!
Start Quiz Now