GRAPH ALGORITHMS
Graph algorithms are essential for solving problems that involve networks, routes, or connections. Below is a breakdown of six key graph algorithms explained in simple terms, with emojis and code examples.
1. Dijkstra’s Algorithm - Shortest Path
Purpose:
Dijkstra's algorithm finds the shortest path from a starting node to all other nodes in a graph, where edge weights are non-negative.
Steps:
Start from the source and assign it a distance of 0.
Set the distance of all other nodes to infinity.
Use a priority queue to always expand the node with the smallest known distance.
Update the neighboring nodes' distances if a shorter path is found.
Repeat until all nodes have been processed.
Use Cases:
GPS Navigation: Routing the shortest path for a driver.
Network Routing: Efficient packet forwarding in communication networks.
#include <iostream>
using namespace std;
void initialize(int Q[], int distance[], int path[], int n) {
for (int i = 0; i < n; i++) {
distance[i] = 99999; // Infinity
path[i] = -1; // No previous node
Q[i] = 1; // All nodes unvisited
}
}
int deleteMin(int Q[], int priority[], int n) {
int min_vertex = -1;
int min_value = 99999; // Infinity
for (int i = 0; i < n; i++) {
if (Q[i] == 1 && priority[i] < min_value) {
min_value = priority[i];
min_vertex = i;
}
}
if (min_vertex != -1) {
Q[min_vertex] = 0; // Mark as visited
}
return min_vertex;
}
void decrease(int Q[], int priority[], int v, int value) {
if (Q[v] == 1 && value < priority[v]) {
priority[v] = value;
}
}
void dijkstra(int graph[][100], int n, int source) {
int Q[100], distance[100], path[100];
initialize(Q, distance, path, n);
distance[source] = 0;
decrease(Q, distance, source, 0);
for (int i = 0; i < n; i++) {
int u = deleteMin(Q, distance, n);
if (u == -1) break;
for (int v = 0; v < n; v++) {
if (graph[u][v] != 0 && Q[v] == 1) {
if (distance[u] + graph[u][v] < distance[v]) {
distance[v] = distance[u] + graph[u][v];
path[v] = u;
decrease(Q, distance, v, distance[v]);
}
}
}
}
cout << "Vertex\tDistance\tPath" << endl;
for (int i = 0; i < n; i++) {
cout << i + 1 << "\t" << distance[i] << "\t\t";
if (path[i] != -1)
cout << path[i] + 1;
else
cout << "null";
cout << endl;
}
}
int main() {
int n = 6;
int graph[100][100] = {
{0, 7, 9, 0, 0, 14},
{7, 0, 10, 15, 0, 0},
{9, 10, 0, 11, 0, 2},
{0, 15, 11, 0, 6, 0},
{0, 0, 0, 6, 0, 9},
{14, 0, 2, 0, 9, 0}
};
int source = 0;
dijkstra(graph, n, source);
return 0;
}
1. Floyd-Warshall Algorithm - All-Pairs Shortest Path 🌍
Purpose:
The Floyd-Warshall algorithm calculates the shortest paths between all pairs of nodes in a graph, providing a complete solution for finding all possible shortest paths.
Steps:
Initialize a distance matrix where each element represents the distance between two nodes.
Iteratively update the matrix by checking if a shorter path exists through an intermediate node.
Repeat this process for all pairs of nodes to ensure the shortest paths are found.
Use Cases:
Small to Medium Graphs: Ideal for graphs where calculating paths between all node pairs is needed.
Social Network Analysis 📱: Analyzing connections and finding shortest paths between users in social networks.
/ Floyd-Warshall Algorithm to find all-pairs shortest paths
void floydWarshall(int graph[][100], int n) {
int dist[100][100];
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
dist[i][j] = graph[i][j];
}
}
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] + dist[k][j] < dist[i][j]) {
dist[i][j] = dist[i][k] + dist[k][j];
}
}
}
}
// Print shortest distance matrix
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cout << dist[i][j] << " ";
}
cout << endl;
}
}
3. Warshall’s Algorithm 🔄 (Transitive Closure)
Purpose:
Find if there’s a path between each pair of nodes in a directed graph.
Steps:
Create an adjacency matrix.
Update the matrix to reflect if a path exists from node i to node j through other nodes.
Use Cases:
Graph connectivity 🔗
Reachability analysis 🔍
Code Example:
// Warshall's Algorithm to compute Transitive Closure
void warshall(int graph[][100], int n) {
int R[100][100];
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
R[i][j] = graph[i][j];
}
}
for (int k = 0; k < n; k++) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
R[i][j] = R[i][j] || (R[i][k] && R[k][j]);
}
}
}
// Print Transitive Closure Matrix
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cout << R[i][j] << " ";
}
cout << endl;
}
}
4. Kruskal’s Algorithm
Find the Minimum Spanning Tree (MST) of a graph, which connects all nodes with the minimum total edge weight.
Steps:
Sort all edges by weight.
Add edges to the MST, ensuring no cycles are formed using the union-find technique.
Stop when the MST contains n-1 edges.
Use Cases:
Network design (e.g., laying cables) 🖥️
Clustering 🧩
Code Example:
#include <iostream>
using namespace std;
struct Graph {
int u[50], v[50], weight[50];
};
void read(Graph &g, int E) {
cout << "Enter edges (u, v, weight):" << endl;
for (int i = 1; i <= E; i++) {
cin >> g.u[i] >> g.v[i] >> g.weight[i];
}
}
void kruskal(int V, int E, Graph &g) {
// Sorting edges based on weights (simple bubble sort)
for (int i = 1; i <= E - 1; i++) {
for (int j = 1; j <= E - i; j++) {
if (g.weight[j] > g.weight[j + 1]) {
swap(g.u[j], g.u[j + 1]);
swap(g.v[j], g.v[j + 1]);
swap(g.weight[j], g.weight[j + 1]);
}
}
}
// Implementing Union-Find and MST construction
int parent[50];
for (int i = 0; i < V; i++) parent[i] = i;
int mst_weight = 0;
for (int i = 1; i <= E; i++) {
// Add edge to MST if no cycle is formed
// Union-Find logic
}
cout << "Total weight of MST: " << mst_weight << endl;
}
5. Prim’s Algorithm 🌲 (Minimum Spanning Tree)
Purpose:
Find the Minimum Spanning Tree (MST) by growing the tree from any starting node. It starts from an arbitrary node and progressively adds the smallest edge that connects a node in the MST to a node outside of it.
Steps:
Start from any node and mark it as part of the MST.
Add the smallest edge that connects a node in the MST to a node outside the MST.
Repeat until all nodes are included in the MST.
Code Example:
#include <iostream>
#include <climits>
using namespace std;
#define MAX 100
// Function to find the node with the minimum edge weight
int minKey(int key[], bool mstSet[], int V) {
int min = INT_MAX, minIndex;
// Loop through all vertices to find the one with the smallest key value
for (int v = 0; v < V; v++) {
if (!mstSet[v] && key[v] < min) {
min = key[v];
minIndex = v;
}
}
return minIndex;
}
// Function to implement Prim's Algorithm
void primMST(int graph[MAX][MAX], int V) {
int parent[MAX]; // Array to store the MST
int key[MAX]; // Key values used to pick minimum weight edge
bool mstSet[MAX]; // To track vertices included in MST
// Initialize all keys as infinite, mstSet as false, and parent as -1
for (int i = 0; i < V; i++) {
key[i] = INT_MAX;
mstSet[i] = false;
parent[i] = -1;
}
// Choose the first vertex and set its key to 0
key[0] = 0;
// The MST will have V vertices
for (int count = 0; count < V - 1; count++) {
// Get the vertex with the minimum key value
int u = minKey(key, mstSet, V);
// Add this vertex to the MST set
mstSet[u] = true;
// Update the key values of the adjacent vertices of the selected vertex
for (int v = 0; v < V; v++) {
// graph[u][v] is non-zero only if there is an edge from u to v
if (graph[u][v] && !mstSet[v] && graph[u][v] < key[v]) {
parent[v] = u;
key[v] = graph[u][v];
}
}
}
// Print the constructed MST
cout << "Edge \tWeight\n";
for (int i = 1; i < V; i++) {
cout << parent[i] + 1 << " - " << i + 1 << " \t" << graph[i][parent[i]] << endl;
}
}
int main() {
// Sample graph represented as an adjacency matrix
int graph[MAX][MAX] = {
{0, 2, 0, 6, 0, 0},
{2, 0, 3, 8, 5, 0},
{0, 3, 0, 0, 7, 0},
{6, 8, 0, 0, 9, 1},
{0, 5, 7, 9, 0, 4},
{0, 0, 0, 1, 4, 0}
};
int V = 6; // Number of vertices
// Call the Prim's algorithm function
primMST(graph, V);
return 0;
}
Sample Output:
Edge Weight
1 - 2 2
2 - 3 3
1 - 5 5
4 - 5 4
4 - 6 1