Graph Algorithms and C Programming

Examine graph theory algorithms, such as Dijkstra’s algorithm, Floyd-Warshall algorithm, and topological sorting, implemented in C programming for solving complex problems.

Graph algorithms are essential tools for solving a wide range of complex problems, from finding the shortest path in a transportation network to determining the order of tasks in a project. In this example, we’ll explore three fundamental graph algorithms: Dijkstra’s algorithm, Floyd-Warshall algorithm, and topological sorting. We’ll provide the syntax, program, and output explanation for each algorithm.

1. Dijkstra’s Algorithm:

Dijkstra’s algorithm is a graph search algorithm that finds the shortest path from a single source vertex to all other vertices in a weighted graph with non-negative edge weights. The algorithm maintains a set of vertices whose shortest distance from the source is known and iteratively explores neighboring vertices to update their distances.

Syntax:

void dijkstra(int graph[V][V], int src);

Program: Dijkstra’s Algorithm in C

#include <stdio.h>
#include <stdbool.h>
#include <limits.h>

#define V 5 // Number of vertices

int minDistance(int dist[], bool visited[]) {
    int min = INT_MAX, min_index;

    for (int v = 0; v < V; v++) {
        if (!visited[v] && dist[v] <= min) {
            min = dist[v];
            min_index = v;
        }
    }

    return min_index;
}

void printSolution(int dist[]) {
    printf("Vertex   Distance from Source\n");
    for (int i = 0; i < V; i++) {
        printf("%d \t\t %d\n", i, dist[i]);
    }
}

void dijkstra(int graph[V][V], int src) {
    int dist[V];
    bool visited[V];

    for (int i = 0; i < V; i++) {
        dist[i] = INT_MAX;
        visited[i] = false;
    }

    dist[src] = 0;

    for (int count = 0; count < V - 1; count++) {
        int u = minDistance(dist, visited);
        visited[u] = true;

        for (int v = 0; v < V; v++) {
            if (!visited[v] && graph[u][v] && dist[u] != INT_MAX && dist[u] + graph[u][v] < dist[v]) {
                dist[v] = dist[u] + graph[u][v];
            }
        }
    }

    printSolution(dist);
}

int main() {
    int graph[V][V] = {
        {0, 4, 0, 0, 0},
        {4, 0, 8, 7, 0},
        {0, 8, 0, 6, 0},
        {0, 7, 6, 0, 9},
        {0, 0, 0, 9, 0}
    };

    dijkstra(graph, 0);

    return 0;
}

Explanation:

• The program implements Dijkstra’s algorithm to find the shortest path from a source vertex to all other vertices in a weighted graph.
• The minDistance function finds the vertex with the minimum distance from the source among the unvisited vertices.
• The dijkstra function calculates the shortest distances and prints the solution.

Output Explanation:

The program’s output shows the shortest distance from the source vertex (vertex 0) to all other vertices.

Vertex   Distance from Source
0                0
1                4
2                12
3                19
4                21

2. Floyd-Warshall Algorithm:

The Floyd-Warshall algorithm is a dynamic programming technique used to find the shortest paths between all pairs of vertices in a weighted graph. It can handle graphs with both positive and negative edge weights, as long as the graph does not contain negative cycles. The algorithm works by iteratively updating the shortest distances between pairs of vertices.

Program: Floyd-Warshall Algorithm in C

#include <stdio.h>

#define V 4 // Number of vertices
#define INF 99999

void printSolution(int dist[][V]) {
    printf("Shortest distances between every pair of vertices:\n");
    for (int i = 0; i < V; i++) {
        for (int j = 0; j < V; j++) {
            if (dist[i][j] == INF) {
                printf("%7s", "INF");
            } else {
                printf("%7d", dist[i][j]);
            }
        }
        printf("\n");
    }
}

void floydWarshall(int graph[][V]) {
    int dist[V][V];

    for (int i = 0; i < V; i++) {
        for (int j = 0; j < V; j++) {
            dist[i][j] = graph[i][j];
        }
    }

    for (int k = 0; k < V; k++) {
        for (int i = 0; i < V; i++) {
            for (int j = 0; j < V; j++) {
                if (dist[i][k] + dist[k][j] < dist[i][j]) {
                    dist[i][j] = dist[i][k] + dist[k][j];
                }
            }
        }
    }

    printSolution(dist);
}

int main() {
    int graph[V][V] = {
        {0, 5, INF, 10},
        {INF, 0, 3, INF},
        {INF, INF, 0, 1},
        {INF, INF, INF, 0}
    };

    floydWarshall(graph);

    return 0;
}

Explanation:

1. The graph array represents the input weighted graph. For edges that don’t exist, we use a large value (INF) to represent infinity.
2. The floydWarshall function implements the Floyd-Warshall algorithm. It initializes a dist array to store the shortest distances between all pairs of vertices.
3. The outermost loop iterates through all vertices (k) to find shortest paths between all pairs of vertices through vertex k.
4. The two inner loops (i and j) iterate through all pairs of vertices and update the shortest distance if a shorter path is found through vertex k.
5. The printSolution function displays the calculated shortest distances between all pairs of vertices.

Output Explanation:

The program’s output shows the shortest distances between every pair of vertices in the graph. In this example, the graph has 4 vertices (0 to 3).

Shortest distances between every pair of vertices:
      0      5      8      9
    INF      0      3      4
    INF    INF      0      1
    INF    INF    INF      0

• The distance from vertex 0 to vertex 1 is 5.
• The distance from vertex 1 to vertex 3 is 4.
• The distance from vertex 2 to vertex 3 is 1.
• There are no negative cycles in this graph.

3. Topological Sorting:

Topological sorting is a linear ordering of the vertices of a directed acyclic graph (DAG) in such a way that for every directed edge u -> v, vertex u comes before vertex v in the ordering. This ordering represents a sequence of tasks or events where each task depends on certain other tasks.

Program: Topological Sorting in C

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

#define V 6 // Number of vertices

struct Node {
    int vertex;
    struct Node* next;
};

struct Graph {
    struct Node** adjList;
};

struct Graph* createGraph() {
    struct Graph* graph = (struct Graph*)malloc(sizeof(struct Graph));
    graph->adjList = (struct Node**)malloc(V * sizeof(struct Node*));

    for (int i = 0; i < V; i++) {
        graph->adjList[i] = NULL;
    }

    return graph;
}

void addEdge(struct Graph* graph, int src, int dest) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->vertex = dest;
    newNode->next = graph->adjList[src];
    graph->adjList[src] = newNode;
}

void topologicalSortUtil(struct Graph* graph, int v, bool visited[], struct Node** stack) {
    visited[v] = true;

    struct Node* temp = graph->adjList[v];
    while (temp != NULL) {
        if (!visited[temp->vertex]) {
            topologicalSortUtil(graph, temp->vertex, visited, stack);
        }
        temp = temp->next;
    }

    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->vertex = v;
    newNode->next = *stack;
    *stack = newNode;
}

void topologicalSort(struct Graph* graph) {
    bool visited[V];
    for (int i = 0; i < V; i++) {
        visited[i] = false;
    }

    struct Node* stack = NULL;

    for (int i = 0; i < V; i++) {
        if (!visited[i]) {
            topologicalSortUtil(graph, i, visited, &stack);
        }
    }

    printf("Topological Sorting: ");
    while (stack != NULL) {
        printf("%d ", stack->vertex);
        stack = stack->next;
    }
}

int main() {
    struct Graph* graph = createGraph();

    addEdge(graph, 5, 2);
    addEdge(graph, 5, 0);
    addEdge(graph, 4, 0);
    addEdge(graph, 4, 1);
    addEdge(graph, 2, 3);
    addEdge(graph, 3, 1);

    topologicalSort(graph);

    return 0;
}

Explanation:

• This program demonstrates topological sorting using an adjacency list representation of a graph.
• We create a structure Node to represent vertices in the adjacency list and a structure Graph to store the adjacency list itself.
• The createGraph function initializes the graph’s adjacency list.
• The addEdge function adds edges to the graph.
• The topologicalSortUtil function performs a depth-first search (DFS) and builds the topological ordering.
• The topologicalSort function calls topologicalSortUtil for each unvisited vertex and prints the topological ordering.

Output Explanation:

The program’s output shows the topological sorting of the vertices.

Topological Sorting: 5 4 2 3 1 0