Dijkstra's Algorithm Lists

-

 #include <stdio.h>

#include <stdlib.h>

#include <limits.h>


#define MAX 100

#define INF INT_MAX


typedef struct Edge {

    int dest;

    int weight;

    struct Edge* next;

} Edge;


typedef struct Graph {

    Edge* edges[MAX];

} Graph;


int dist[MAX];

int pred[MAX];

int visited[MAX];


void create_graph(Graph* graph, int n, int gtype);

void dijkstra(Graph* graph, int n, int source);

void print_shortest_path(int source, int destination);


int main() {

    int n, gtype, source;

    printf("Enter 1 for undirected graph and -1 for directed graph: ");

    scanf("%d", &gtype);

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

    scanf("%d", &n);

    

    Graph graph = { {NULL} };

    create_graph(&graph, n, gtype);

    

    printf("Enter the source vertex: ");

    scanf("%d", &source);

    dijkstra(&graph, n, source);


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

        if (i != source) {

            printf("Shortest path from vertex %d to vertex %d: ", source, i);

            print_shortest_path(source, i);

            printf("\n");

        }

    }

    return 0;

}


void create_graph(Graph* graph, int n, int gtype) {

    int max_edges, src, dest, weight;


    if (gtype == 1)

        max_edges = (n * (n - 1)) / 2;

    else if (gtype == -1)

        max_edges = n * (n - 1);


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

        printf("Enter edge %d (source, destination, weight) (to quit enter -1 -1 -1): ", i + 1);

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

        if (src == -1 && dest == -1 && weight == -1)

            break;


        if (src < 0 || dest < 0 || src >= n || dest >= n) {

            printf("Invalid source or destination!\n");

            i--;

        } else {

            Edge* edge = (Edge*)malloc(sizeof(Edge));

            edge->dest = dest;

            edge->weight = weight;

            edge->next = graph->edges[src];

            graph->edges[src] = edge;


            if (gtype == 1) {

                edge = (Edge*)malloc(sizeof(Edge));

                edge->dest = src;

                edge->weight = weight;

                edge->next = graph->edges[dest];

                graph->edges[dest] = edge;

            }

        }

    }


    printf("Adjacency List is:\n");

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

        printf("%d: ", i);

        for (Edge* edge = graph->edges[i]; edge != NULL; edge = edge->next) {

            printf("-> %d (%d) ", edge->dest, edge->weight);

        }

        printf("\n");

    }

}


void dijkstra(Graph* graph, int n, int source) {

    int count, mindist, nextnode;


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

        dist[i] = INF;

        pred[i] = -1;

        visited[i] = 0;

    }


    dist[source] = 0;

    visited[source] = 1;

    count = 1;


    while (count < n) {

        mindist = INF;

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

            if (dist[i] < mindist && !visited[i]) {

                mindist = dist[i];

                nextnode = i;

            }

        }


        visited[nextnode] = 1;

        for (Edge* edge = graph->edges[nextnode]; edge != NULL; edge = edge->next) {

            if (!visited[edge->dest]) {

                if (dist[nextnode] + edge->weight < dist[edge->dest]) {

                    dist[edge->dest] = dist[nextnode] + edge->weight;

                    pred[edge->dest] = nextnode;

                }

            }

        }

        count++;

    }

}


void print_shortest_path(int source, int destination) {

    if (destination == source) {

        printf("%d", source);

    } else if (pred[destination] == source) {

        printf("%d -> %d ", source, destination);

    } else {

        print_shortest_path(source, pred[destination]);

        printf("-> %d ", destination);

    }

}


Comments

Post a Comment

Popular posts from this blog

AVL Trees

-
#include <stdio.h> #include <stdlib.h> // Structure to represent a node in the AVL tree struct Node {     int key;     struct Node* left;     struct Node* right;     int height; }; // Function to get the height of the node int height(struct Node* N) {     if (N == NULL)         return 0;     return N->height; } // Function to get the maximum of two integers int max(int a, int b) {     return (a > b) ? a : b; } // Helper function that allocates a new node with the given key struct Node* newNode(int key) {     struct Node* node = (struct Node*)malloc(sizeof(struct Node));     node->key = key;     node->left = NULL;     node->right = NULL;     node->height = 1; // New node is initially added at leaf     return(node); } // Right rotate subtree rooted with y struct Node* rightRotate(struct Node* y) {     ...
Read more

BFS Matrix

-
#include<stdio.h> #include<stdlib.h> #define MAX 100 #define initial 1 #define waiting 2 #define visited 3 int adj[MAX][MAX];   int state[MAX];      int queue[MAX], front = -1, rear = -1;  void create_graph(int n, int gtype); void BF_Traversal(int n); void BFS(int v, int n); void insert_queue(int vertex); int delete_queue(); int isEmpty_queue(); int main() {     int n, gtype;          printf("Enter 1 for undirected graph and -1 for directed graph: ");     scanf("%d", &gtype);     printf("Enter the number of vertices: ");     scanf("%d", &n);          create_graph(n, gtype);          BF_Traversal(n);          return 0; } void create_graph(int n, int gtype) {     int max_edges, src, dest;          if (gtype == 1)         max_edges = (n * (n - 1)) /...
Read more

BFS List

-
#include<stdio.h> #include<stdlib.h> #define MAX 100 #define initial 1 #define waiting 2 #define visited 3 struct Node { int vertex; struct Node* next; }; int queue[MAX],front=-1,rear=-1; int state[MAX]; struct Node* adj[MAX]; void create_graph(int n,int gtype); void insert_queue(int v); int delete_queue(); int isEmpty_queue(); void BFT(int n); void BFS(int start,int n); void add_edge(int src,int dest); struct Node* create_node(int v); int main() { int gtype,n; printf("Enter 1 for undirected graph and -1 for directed graph:"); scanf("%d",&gtype); printf("Enter the number of vertices:"); scanf("%d",&n); create_graph(n,gtype); BFT(n); return 0; } void create_graph(int n,int gtype) { int max_edges,src,dest; if(gtype==1) max_edges=(n*(n-1))/2; else if(gtype==-1) max_edges=(n*(n-1)); for(int i=0;i<n;i++) adj[i]=NULL; for(int i=0;i<max_edges;i++) { printf("Enter edge %d (press -1 and -1 to quit):...
Read more