Chapter 19: Advanced Graph Algorithms
Welcome to Chapter 19, where we’ll explore some of the more advanced algorithms used in graph theory. These algorithms are crucial for solving complex problems related to networks, paths, and flows. In this chapter, we will cover:
-
Shortest Path Algorithms:
- Dijkstra’s Algorithm
- Bellman-Ford Algorithm
-
Maximum Flow Algorithms:
- Ford-Fulkerson Method
- Edmonds-Karp Algorithm
19.1 Shortest Path Algorithms
In graph theory, finding the shortest path between two nodes is a common problem. Depending on the type of graph (directed, undirected, weighted, unweighted), different algorithms can be used to find the shortest paths efficiently.
19.1.1 Dijkstra’s Algorithm
Definition:
Dijkstra’s Algorithm finds the shortest path from a source node to all other nodes in a graph with non-negative edge weights. It follows a greedy approach by choosing the shortest path at each step.
How Dijkstra’s Algorithm Works:
- Initialize Distances: Start by assigning an infinite distance to all nodes except the source node, which gets a distance of 0.
- Priority Queue: Use a priority queue to select the node with the smallest known distance.
- Relaxation: For each neighboring node, check if a shorter path can be found through the current node. If so, update the distance.
- Repeat: Continue this process until all nodes have been visited and their shortest paths are known.
Dijkstra’s Algorithm Example:
Consider the graph below:
A --1--> B
A --4--> C
B --2--> C
B --6--> D
C --3--> D
To find the shortest path from A to all other nodes:
-
Initialization: Set the distance to A as 0, and all others as infinity:
- Distances: A = 0, B = ∞, C = ∞, D = ∞
-
Priority Queue: Start with A (0).
-
Relaxation:
- From A, update B (0 + 1 = 1) and C (0 + 4 = 4).
- New distances: A = 0, B = 1, C = 4, D = ∞
-
Next Node: Select B (1), update C (1 + 2 = 3) and D (1 + 6 = 7).
- New distances: A = 0, B = 1, C = 3, D = 7
-
Next Node: Select C (3), update D (3 + 3 = 6).
- Final distances: A = 0, B = 1, C = 3, D = 6
The shortest paths from A are:
- A to B: 1
- A to C: 3
- A to D: 6
Dijkstra’s Algorithm Implementation in C++:
#include <iostream>
#include <vector>
#include <queue>
#include <limits.h>
using namespace std;
#define INF INT_MAX
// Structure for a graph edge
struct Edge {
int dest, weight;
};
// Dijkstra's algorithm to find the shortest path
void dijkstra(vector<vector<Edge>>& graph, int src) {
int V = graph.size();
vector<int> dist(V, INF);
dist[src] = 0;
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
pq.push({0, src});
while (!pq.empty()) {
int u = pq.top().second;
pq.pop();
for (auto edge : graph[u]) {
int v = edge.dest;
int weight = edge.weight;
if (dist[u] + weight < dist[v]) {
dist[v] = dist[u] + weight;
pq.push({dist[v], v});
}
}
}
cout << "Vertex\tDistance from Source\n";
for (int i = 0; i < V; ++i)
cout << i << "\t\t" << dist[i] << "\n";
}
int main() {
int V = 5;
vector<vector<Edge>> graph(V);
graph[0].push_back({1, 10});
graph[0].push_back({4, 5});
graph[1].push_back({2, 1});
graph[2].push_back({3, 4});
graph[4].push_back({1, 3});
graph[4].push_back({2, 9});
dijkstra(graph, 0);
return 0;
}
This code illustrates Dijkstra’s algorithm for a graph with 5 vertices.
19.1.2 Bellman-Ford Algorithm
Definition:
The Bellman-Ford Algorithm is another method for finding the shortest path from a source node to all other nodes, but unlike Dijkstra’s algorithm, it works with graphs that may contain negative weight edges.
How Bellman-Ford Algorithm Works:
- Initialize Distances: Set the distance of the source node to 0 and all other nodes to infinity.
- Relax All Edges: For each edge, update the distance to its destination if a shorter path is found through the source.
- Repeat: Perform the relaxation process V-1 times, where V is the number of vertices.
- Negative Cycle Detection: In the final pass, check for any further distance reductions. If found, a negative weight cycle exists.
Example:
Consider the graph:
A --1--> B
B --2--> C
C --(-1)--> A
B --3--> D
To find the shortest path from A:
- Initialize distances: A = 0, B = ∞, C = ∞, D = ∞.
- After the first pass:
- A to B: 1
- B to C: 1 + 2 = 3
- B to D: 1 + 3 = 4
- After the second pass, no changes occur, confirming the final shortest paths.
Bellman-Ford Algorithm Implementation in C++:
#include <iostream>
#include <vector>
using namespace std;
struct Edge {
int u, v, weight;
};
void bellmanFord(int V, int E, vector<Edge>& edges, int src) {
vector<int> dist(V, INT_MAX);
dist[src] = 0;
for (int i = 1; i <= V - 1; i++) {
for (int j = 0; j < E; j++) {
int u = edges[j].u;
int v = edges[j].v;
int weight = edges[j].weight;
if (dist[u] != INT_MAX && dist[u] + weight < dist[v]) {
dist[v] = dist[u] + weight;
}
}
}
// Check for negative-weight cycles
for (int i = 0; i < E; i++) {
int u = edges[i].u;
int v = edges[i].v;
int weight = edges[i].weight;
if (dist[u] != INT_MAX && dist[u] + weight < dist[v]) {
cout << "Graph contains a negative-weight cycle\n";
return;
}
}
cout << "Vertex\tDistance from Source\n";
for (int i = 0; i < V; i++)
cout << i << "\t\t" << dist[i] << "\n";
}
int main() {
int V = 5, E = 8;
vector<Edge> edges = {{0, 1, -1}, {0, 2, 4}, {1, 2, 3}, {1, 3, 2}, {1, 4, 2}, {3, 2, 5}, {3, 1, 1}, {4, 3, -3}};
bellmanFord(V, E, edges, 0);
return 0;
}
The Bellman-Ford algorithm is more versatile than Dijkstra’s because it can handle negative weights but is less efficient in practice.
19.2 Maximum Flow Algorithms
In network flow problems, we aim to send as much flow as possible from a source node to a destination node, subject to capacity limits on the edges. Two classic algorithms for finding the maximum flow in a network are Ford-Fulkerson and Edmonds-Karp.
19.2.1 Ford-Fulkerson Method
Definition:
The Ford-Fulkerson Method is a greedy approach to finding the maximum flow in a flow network. It uses augmenting paths to increase the flow until no more paths can be found.
How Ford-Fulkerson Works:
- Initialize Flow: Start with zero flow in all edges.
- Find Augmenting Paths: Look for paths from the source to the sink that can carry more flow.
- Update Flows: Once a path is found, update the flow along the path.
- Repeat: Repeat this process until no augmenting paths are found.
Ford-Fulkerson Example:
Consider a graph
with capacities on each edge:
A --3--> B --2--> C
A --2--> D --3--> C
To find the maximum flow from A to C:
- Start with flow = 0.
- Augmenting path: A -> B -> C with flow = 2.
- Augmenting path: A -> D -> C with flow = 2.
Total flow = 4.
Ford-Fulkerson Implementation in C++:
#include <iostream>
#include <limits.h>
#include <string.h>
#include <queue>
using namespace std;
#define V 6 // Number of vertices in the graph
/* Returns true if there is a path from source 's' to sink 't' in
residual graph. Also fills parent[] to store the path */
bool bfs(int rGraph[V][V], int s, int t, int parent[]) {
bool visited[V];
memset(visited, 0, sizeof(visited));
// Create a queue, enqueue source vertex and mark source vertex as visited
queue<int> q;
q.push(s);
visited[s] = true;
parent[s] = -1;
// Standard BFS Loop
while (!q.empty()) {
int u = q.front();
q.pop();
for (int v = 0; v < V; v++) {
if (visited[v] == false && rGraph[u][v] > 0) { // If not visited and there's capacity
// If we find a connection to the sink node, return true
if (v == t) {
parent[v] = u;
return true;
}
q.push(v);
parent[v] = u;
visited[v] = true;
}
}
}
// If we reached sink in BFS starting from source, then return true
return false;
}
// Returns the maximum flow from s to t in the given graph
int fordFulkerson(int graph[V][V], int s, int t) {
int u, v;
// Create a residual graph and fill the residual graph with given capacities in the original graph
int rGraph[V][V]; // Residual graph where rGraph[i][j] indicates residual capacity
for (u = 0; u < V; u++)
for (v = 0; v < V; v++)
rGraph[u][v] = graph[u][v];
int parent[V]; // This array is filled by BFS and stores the path
int max_flow = 0; // There is no flow initially
// Augment the flow while there is a path from source to sink
while (bfs(rGraph, s, t, parent)) {
// Find the maximum flow through the path found by BFS
int path_flow = INT_MAX;
for (v = t; v != s; v = parent[v]) {
u = parent[v];
path_flow = min(path_flow, rGraph[u][v]);
}
// update residual capacities of the edges and reverse edges along the path
for (v = t; v != s; v = parent[v]) {
u = parent[v];
rGraph[u][v] -= path_flow;
rGraph[v][u] += path_flow;
}
// Add the path flow to the overall flow
max_flow += path_flow;
}
return max_flow;
}
int main() {
// Let us create a graph shown in the above example
int graph[V][V] = {
{0, 16, 13, 0, 0, 0},
{0, 0, 10, 12, 0, 0},
{0, 4, 0, 0, 14, 0},
{0, 0, 9, 0, 0, 20},
{0, 0, 0, 7, 0, 4},
{0, 0, 0, 0, 0, 0}
};
cout << "The maximum possible flow is " << fordFulkerson(graph, 0, 5);
return 0;
}
19.2.2 Edmonds-Karp Algorithm
Definition:
The Edmonds-Karp Algorithm is an implementation of Ford-Fulkerson that uses breadth-first search (BFS) to find augmenting paths. It guarantees polynomial time complexity.
Edmonds-Karp Implementation in C++:
#include <iostream>
#include <limits.h>
#include <queue>
#include <string.h>
using namespace std;
#define V 6 // Number of vertices in the graph
// A BFS based function to check if there is a path from source to sink in residual graph.
// Also fills parent[] to store the path
bool bfs(int rGraph[V][V], int s, int t, int parent[]) {
bool visited[V];
memset(visited, 0, sizeof(visited));
queue<int> q;
q.push(s);
visited[s] = true;
parent[s] = -1;
// Standard BFS loop
while (!q.empty()) {
int u = q.front();
q.pop();
for (int v = 0; v < V; v++) {
if (visited[v] == false && rGraph[u][v] > 0) {
if (v == t) {
parent[v] = u;
return true;
}
q.push(v);
parent[v] = u;
visited[v] = true;
}
}
}
return false;
}
// Function to return the maximum flow from s to t in the given graph
int edmondsKarp(int graph[V][V], int s, int t) {
int u, v;
int rGraph[V][V]; // Residual graph
for (u = 0; u < V; u++)
for (v = 0; v < V; v++)
rGraph[u][v] = graph[u][v];
int parent[V]; // To store path from BFS
int max_flow = 0; // No flow initially
// Augment the flow while there is a path from source to sink
while (bfs(rGraph, s, t, parent)) {
// Find minimum residual capacity of the augmenting path
int path_flow = INT_MAX;
for (v = t; v != s; v = parent[v]) {
u = parent[v];
path_flow = min(path_flow, rGraph[u][v]);
}
// Update residual capacities and reverse edges along the path
for (v = t; v != s; v = parent[v]) {
u = parent[v];
rGraph[u][v] -= path_flow;
rGraph[v][u] += path_flow;
}
max_flow += path_flow;
}
return max_flow;
}
int main() {
int graph[V][V] = {
{0, 16, 13, 0, 0, 0},
{0, 0, 10, 12, 0, 0},
{0, 4, 0, 0, 14, 0},
{0, 0, 9, 0, 0, 20},
{0, 0, 0, 7, 0, 4},
{0, 0, 0, 0, 0, 0}
};
cout << "The maximum possible flow is " << edmondsKarp(graph, 0, 5) << endl;
return 0;
}
In this chapter, we covered some of the most important algorithms in graph theory, including shortest path and maximum flow algorithms. These techniques are foundational for solving real-world problems in routing, network design, and resource allocation.
In the next chapter, we will explore dynamic programming and its applications in optimization problems!
