4. Dijkstra's algorithm

  #include <stdio.h>

#include <stdbool.h>

#include <limits.h>

#define MAX_VERTICES 10  // Maximum number of vertices

#define INF INT_MAX

int minDistance(int dist[], bool sptSet[], int V) {

    int min = INF, min_index;

    for (int v = 0; v < V; v++)

        if (sptSet[v] == false && dist[v] <= min)

            min = dist[v], min_index = v;

    return min_index;

}

void printSolution(int dist[], int V) {

    printf("Vertex \t\t Distance from Source\n");

    for (int i = 0; i < V; i++)

        printf("%d \t\t %d\n", i, dist[i]);

}

void dijkstra(int graph[MAX_VERTICES][MAX_VERTICES], int src, int V) {

    int dist[MAX_VERTICES]; 

    bool sptSet[MAX_VERTICES]; 

    // Initialize all distances as INFINITE and sptSet[] as false

    for (int i = 0; i < V; i++)

        dist[i] = INF, sptSet[i] = false;

    dist[src] = 0;

    // Find shortest path for all vertices

    for (int count = 0; count < V - 1; count++) {

        int u = minDistance(dist, sptSet, V);

        sptSet[u] = true;

        for (int v = 0; v < V; v++)

            if (!sptSet[v] && graph[u][v] && dist[u] != INF && dist[u] + graph[u][v] < dist[v])

                dist[v] = dist[u] + graph[u][v];

    }

    printSolution(dist, V);

}

int main() {

    int V, E;

    printf("Enter the number of vertices: ");

    scanf("%d", &V);

    printf("Enter the number of edges: ");

    scanf("%d", &E);

    int graph[MAX_VERTICES][MAX_VERTICES] = {{0}};

    printf("Enter the source vertex, destination vertex, and weight for each edge:\n");

    for (int i = 0; i < E; i++) {

        int source, dest, weight;

        scanf("%d %d %d", &source, &dest, &weight);

        graph[source][dest] = weight;

        graph[dest][source] = weight; // Assuming undirected graph

    }

    dijkstra(graph, 0, V);

    return 0;

}

OUTPUT:

vertices:5

edges;7

0 1 2

0 3 6

1 2 3

1 3 8

1 4 5

2 4 7

3 4 9