Scribd Logo
Upload

Welcome to Scribd!

  • 5 views

    Ada PGM 4

    Uploaded by

    md.afnankhaja

    Copyright:

    © All Rights Reserved
    Download as TXT, PDF, TXT or read online from Scribd

    Ada PGM 4

    Uploaded by

    md.afnankhaja
    5 views4 pages

    Original Title

    ada pgm 4

    Copyright

    © © All Rights Reserved

    Available Formats

    TXT, PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    Copyright:

    © All Rights Reserved
    Download as TXT, PDF, TXT or read online from Scribd
    Download as txt, pdf, or txt
    5 views4 pages

    Ada PGM 4

    Uploaded by

    md.afnankhaja

    Copyright:

    © All Rights Reserved
    Download as TXT, PDF, TXT or read online from Scribd
    Download as txt, pdf, or txt
    You are on page 1of 4

    // C program for Dijkstra's single source shortest path

    // algorithm.

    #include <stdio.h>
    #include <stdbool.h>
    #define INF 99999
    #define V 5 // Number of vertices

    // A function to find the vertex with the minimum distance value, from the set of
    vertices not yet included in shortest path tree
    int minDistance(int dist[], bool sptSet[]) {
    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;
    }

    // A utility function to print the constructed distance array


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

    // Dijkstra's algorithm for adjacency matrix representation of the graph


    void dijkstra(int graph[V][V], int src) {
    int dist[V]; // The output array. dist[i] will hold the shortest distance from
    src to i
    bool sptSet[V]; // sptSet[i] will be true if vertex i is included in shortest
    path tree

    // 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);
    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);
    }

    // Driver code
    int main() {
    int graph[V][V] = {{0, 9, 6, 5, 3},
    {9, 0, 0, 0, 0},
    {6, 0, 0, 0, 0},
    {5, 0, 0, 0, 0},
    {3, 0, 0, 0, 0}};

    dijkstra(graph, 0);
    return 0;
    }

    Vertex Distance from Source


    0 0
    1 9
    2 6
    3 5
    4 3

    Dijksta's 2

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

    #define MAX_VERTICES 100

    // Function to find the vertex with the minimum distance value


    int minDistance(int dist[], int sptSet[], int vertices) {
    int min = INT_MAX, minIndex;

    for (int v = 0; v < vertices; v++) {


    if (!sptSet[v] && dist[v] < min) {
    min = dist[v];
    minIndex = v;
    }
    }

    return minIndex;
    }

    // Function to print the constructed distance array


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

    // Function to implement Dijkstra's algorithm for a given graph and source vertex
    void dijkstra(int graph[MAX_VERTICES][MAX_VERTICES], int src, int vertices) {
    int dist[MAX_VERTICES]; // The output array dist[i] holds the shortest distance
    from src to i
    int sptSet[MAX_VERTICES]; // sptSet[i] will be true if vertex i is included in
    the shortest path tree or the shortest distance from src to i is finalized

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


    for (int i = 0; i < vertices; i++) {
    dist[i] = INT_MAX;
    sptSet[i] = 0;
    }
    // Distance from source vertex to itself is always 0
    dist[src] = 0;

    // Find the shortest path for all vertices


    for (int count = 0; count < vertices - 1; count++) {
    // Pick the minimum distance vertex from the set of vertices not yet
    processed.
    // u is always equal to src in the first iteration.
    int u = minDistance(dist, sptSet, vertices);

    // Mark the picked vertex as processed


    sptSet[u] = 1;

    // Update dist value of the adjacent vertices of the picked vertex.


    for (int v = 0; v < vertices; v++) {
    // Update dist[v] only if it is not in the sptSet, there is an edge
    from u to v,
    // and the total weight of path from src to v through u is smaller than
    the current value of dist[v]
    if (!sptSet[v] && graph[u][v] && dist[u] != INT_MAX && dist[u] +
    graph[u][v] < dist[v]) {
    dist[v] = dist[u] + graph[u][v];
    }
    }
    }

    // Print the constructed distance array


    printSolution(dist, vertices);
    }

    int main() {
    int vertices;

    // Input the number of vertices


    printf("Input the number of vertices: ");
    scanf("%d", &vertices);

    if (vertices <= 0 || vertices > MAX_VERTICES) {


    printf("Invalid number of vertices. Exiting...\n");
    return 1;
    }

    int graph[MAX_VERTICES][MAX_VERTICES];

    // Input the adjacency matrix representing the weighted graph


    printf("Input the adjacency matrix for the graph (use INT_MAX for infinity):\
    n");
    for (int i = 0; i < vertices; i++) {
    for (int j = 0; j < vertices; j++) {
    scanf("%d", &graph[i][j]);
    }
    }

    int source;

    // Input the source vertex


    printf("Input the source vertex: ");
    scanf("%d", &source);
    if (source < 0 || source >= vertices) {
    printf("Invalid source vertex. Exiting...\n");
    return 1;
    }

    // Perform Dijkstra's algorithm


    dijkstra(graph, source, vertices);

    return 0;
    }

    You might also like