Scribd
Upload
50 views5 pages

Output Code

The document contains C code for implementing Dijkstra's algorithm to find the shortest paths in a graph represented by nodes and edges. It includes structures for edges and a priority queue, functions to initialize node IDs, retrieve hardcoded edges, and perform the Dijkstra algorithm. The main function initializes the nodes and retrieves edges, but is incomplete.

Uploaded by

Shubh Gupta
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as TXT, PDF, TXT or read online on Scribd
50 views5 pages

Output Code

The document contains C code for implementing Dijkstra's algorithm to find the shortest paths in a graph represented by nodes and edges. It includes structures for edges and a priority queue, functions to initialize node IDs, retrieve hardcoded edges, and perform the Dijkstra algorithm. The main function initializes the nodes and retrieves edges, but is incomplete.

Uploaded by

Shubh Gupta
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as TXT, PDF, TXT or read online on Scribd
You are on page 1/ 5

#include <stdio.

h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

#define MAX_NODES 36
#define MAX_EDGES 100
#define MAX_NAME_LENGTH 50

typedef struct {
int u, v, w;
} Edge;

typedef struct {
int dist;
int node;
} PQNode;

typedef struct {
PQNode* heap;
int size;
int capacity;
} PriorityQueue;

// Map to store hardcoded node names and their corresponding IDs


char nodeNames[MAX_NODES][MAX_NAME_LENGTH];
int nodeIDs[MAX_NODES];
int nodeCount = 0;

void initializeNodeIDs() {
strcpy(nodeNames[nodeCount], "Karnataka");
nodeIDs[nodeCount++] = 1;
strcpy(nodeNames[nodeCount], "Andhra_Pradesh");
nodeIDs[nodeCount++] = 2;
strcpy(nodeNames[nodeCount], "Goa");
nodeIDs[nodeCount++] = 3;
strcpy(nodeNames[nodeCount], "Kerala");
nodeIDs[nodeCount++] = 4;
strcpy(nodeNames[nodeCount], "Telangana");
nodeIDs[nodeCount++] = 5;
strcpy(nodeNames[nodeCount], "Tamil_Nadu");
nodeIDs[nodeCount++] = 6;
strcpy(nodeNames[nodeCount], "Maharashtra");
nodeIDs[nodeCount++] = 7;
strcpy(nodeNames[nodeCount], "Delhi");
nodeIDs[nodeCount++] = 8;
strcpy(nodeNames[nodeCount], "Haryana");
nodeIDs[nodeCount++] = 9;
strcpy(nodeNames[nodeCount], "Uttar_Pradesh");
nodeIDs[nodeCount++] = 10;
strcpy(nodeNames[nodeCount], "Uttarakhand");
nodeIDs[nodeCount++] = 11;
strcpy(nodeNames[nodeCount], "Punjab");
nodeIDs[nodeCount++] = 12;
strcpy(nodeNames[nodeCount], "Rajasthan");
nodeIDs[nodeCount++] = 13;
strcpy(nodeNames[nodeCount], "Himachal_Pradesh");
nodeIDs[nodeCount++] = 14;
strcpy(nodeNames[nodeCount], "Manipur");
nodeIDs[nodeCount++] = 15;
strcpy(nodeNames[nodeCount], "Mizoram");
nodeIDs[nodeCount++] = 16;
strcpy(nodeNames[nodeCount], "Nagaland");
nodeIDs[nodeCount++] = 17;
strcpy(nodeNames[nodeCount], "Assam");
nodeIDs[nodeCount++] = 18;
strcpy(nodeNames[nodeCount], "Odisha");
nodeIDs[nodeCount++] = 19;
strcpy(nodeNames[nodeCount], "Jharkhand");
nodeIDs[nodeCount++] = 20;
strcpy(nodeNames[nodeCount], "Chhattisgarh");
nodeIDs[nodeCount++] = 21;
strcpy(nodeNames[nodeCount], "West_Bengal");
nodeIDs[nodeCount++] = 22;
strcpy(nodeNames[nodeCount], "Jammu_and_Kashmir");
nodeIDs[nodeCount++] = 23;
strcpy(nodeNames[nodeCount], "Ladakh");
nodeIDs[nodeCount++] = 24;
strcpy(nodeNames[nodeCount], "Arunachal Pradesh");
nodeIDs[nodeCount++] = 25;
strcpy(nodeNames[nodeCount], "Tripura");
nodeIDs[nodeCount++] = 26;
strcpy(nodeNames[nodeCount], "Lakshadweep");
nodeIDs[nodeCount++] = 27;
strcpy(nodeNames[nodeCount], "Gujarat");
nodeIDs[nodeCount++] = 28;
strcpy(nodeNames[nodeCount], "Dadra_and_Nagar_Haveli_and_Daman_and_Diu");
nodeIDs[nodeCount++] = 29;
strcpy(nodeNames[nodeCount], "Meghalaya");
nodeIDs[nodeCount++] = 30;
strcpy(nodeNames[nodeCount], "Bihar");
nodeIDs[nodeCount++] = 31;
strcpy(nodeNames[nodeCount], "Puducherry");
nodeIDs[nodeCount++] = 32;
strcpy(nodeNames[nodeCount], "Andaman_and_Nicobar_Islands");
nodeIDs[nodeCount++] = 33;
strcpy(nodeNames[nodeCount], "Sikkim");
nodeIDs[nodeCount++] = 34;
strcpy(nodeNames[nodeCount], "Madhya_Pradesh");
nodeIDs[nodeCount++] = 35;
}

Edge* getHardcodedEdges(int* edgeCount) {


static Edge edges[MAX_EDGES];
*edgeCount = 0;

edges[(*edgeCount)++] = (Edge){1, 2, 436};


edges[(*edgeCount)++] = (Edge){1, 3, 170};
edges[(*edgeCount)++] = (Edge){1, 4, 500};
edges[(*edgeCount)++] = (Edge){1, 5, 423};
edges[(*edgeCount)++] = (Edge){1, 6, 564};
edges[(*edgeCount)++] = (Edge){1, 7, 493};
edges[(*edgeCount)++] = (Edge){8, 9, 120};
edges[(*edgeCount)++] = (Edge){8, 10, 416};
edges[(*edgeCount)++] = (Edge){9, 11, 305};
edges[(*edgeCount)++] = (Edge){9, 12, 242};
edges[(*edgeCount)++] = (Edge){9, 13, 291};
edges[(*edgeCount)++] = (Edge){9, 10, 536};
edges[(*edgeCount)++] = (Edge){9, 14, 250};
edges[(*edgeCount)++] = (Edge){15, 16, 193};
edges[(*edgeCount)++] = (Edge){15, 17, 178};
edges[(*edgeCount)++] = (Edge){15, 18, 196};
edges[(*edgeCount)++] = (Edge){19, 20, 296};
edges[(*edgeCount)++] = (Edge){19, 21, 337};
edges[(*edgeCount)++] = (Edge){19, 2, 795};
edges[(*edgeCount)++] = (Edge){19, 22, 363};
edges[(*edgeCount)++] = (Edge){2, 5, 146};
edges[(*edgeCount)++] = (Edge){2, 6, 544};
edges[(*edgeCount)++] = (Edge){2, 21, 637};
edges[(*edgeCount)++] = (Edge){23, 12, 314};
edges[(*edgeCount)++] = (Edge){23, 14, 302};
edges[(*edgeCount)++] = (Edge){23, 24, 168};
edges[(*edgeCount)++] = (Edge){25, 18, 120};
edges[(*edgeCount)++] = (Edge){25, 17, 140};
edges[(*edgeCount)++] = (Edge){11, 10, 404};
edges[(*edgeCount)++] = (Edge){11, 14, 211};
edges[(*edgeCount)++] = (Edge){20, 21, 436};
edges[(*edgeCount)++] = (Edge){20, 31, 165};
edges[(*edgeCount)++] = (Edge){20, 22, 271};
edges[(*edgeCount)++] = (Edge){20, 10, 565};
edges[(*edgeCount)++] = (Edge){12, 14, 174};
edges[(*edgeCount)++] = (Edge){12, 13, 471};
edges[(*edgeCount)++] = (Edge){26, 16, 129};
edges[(*edgeCount)++] = (Edge){26, 18, 268};
edges[(*edgeCount)++] = (Edge){27, 4, 397};
edges[(*edgeCount)++] = (Edge){28, 35, 724};
edges[(*edgeCount)++] = (Edge){28, 29, 298};
edges[(*edgeCount)++] = (Edge){28, 13, 611};
edges[(*edgeCount)++] = (Edge){28, 7, 545};
edges[(*edgeCount)++] = (Edge){3, 7, 522};
edges[(*edgeCount)++] = (Edge){24, 14, 370};
edges[(*edgeCount)++] = (Edge){7, 21, 662};
edges[(*edgeCount)++] = (Edge){7, 35, 497};
edges[(*edgeCount)++] = (Edge){7, 29, 285};
edges[(*edgeCount)++] = (Edge){7, 5, 470};
edges[(*edgeCount)++] = (Edge){13, 10, 667};
edges[(*edgeCount)++] = (Edge){13, 35, 543};
edges[(*edgeCount)++] = (Edge){30, 18, 177};
edges[(*edgeCount)++] = (Edge){10, 31, 477};
edges[(*edgeCount)++] = (Edge){10, 35, 456};
edges[(*edgeCount)++] = (Edge){10, 21, 626};
edges[(*edgeCount)++] = (Edge){21, 35, 466};
edges[(*edgeCount)++] = (Edge){21, 22, 645};
edges[(*edgeCount)++] = (Edge){21, 5, 539};
edges[(*edgeCount)++] = (Edge){17, 16, 371};
edges[(*edgeCount)++] = (Edge){17, 18, 162};
edges[(*edgeCount)++] = (Edge){31, 22, 348};
edges[(*edgeCount)++] = (Edge){16, 18, 337};
edges[(*edgeCount)++] = (Edge){18, 22, 625};
edges[(*edgeCount)++] = (Edge){32, 6, 154};
edges[(*edgeCount)++] = (Edge){32, 33, 1398};
edges[(*edgeCount)++] = (Edge){34, 22, 511};
edges[(*edgeCount)++] = (Edge){4, 6, 262};
edges[(*edgeCount)++] = (Edge){33, 6, 1527};

return edges;
}
void addEdge(Edge** adj, int* adjSize, const Edge* edge) {
adj[edge->u] = realloc(adj[edge->u], (adjSize[edge->u] + 1) * sizeof(Edge));
adj[edge->v] = realloc(adj[edge->v], (adjSize[edge->v] + 1) * sizeof(Edge));
adj[edge->u][adjSize[edge->u]++] = *edge;
adj[edge->v][adjSize[edge->v]++] = *edge;
}

PriorityQueue* createPriorityQueue(int capacity) {


PriorityQueue* pq = (PriorityQueue*)malloc(sizeof(PriorityQueue));
pq->heap = (PQNode*)malloc(capacity * sizeof(PQNode));
pq->size = 0;
pq->capacity = capacity;
return pq;
}

void swap(PQNode* a, PQNode* b) {


PQNode temp = *a;
*a = *b;
*b = temp;
}

void heapifyUp(PriorityQueue* pq, int idx) {


while (idx > 0 && pq->heap[(idx - 1) / 2].dist > pq->heap[idx].dist) {
swap(&pq->heap[(idx - 1) / 2], &pq->heap[idx]);
idx = (idx - 1) / 2;
}
}

void heapifyDown(PriorityQueue* pq, int idx) {


int smallest = idx;
int left = 2 * idx + 1;
int right = 2 * idx + 2;

if (left < pq->size && pq->heap[left].dist < pq->heap[smallest].dist)


smallest = left;

if (right < pq->size && pq->heap[right].dist < pq->heap[smallest].dist)


smallest = right;

if (smallest != idx) {
swap(&pq->heap[idx], &pq->heap[smallest]);
heapifyDown(pq, smallest);
}
}

void push(PriorityQueue* pq, int dist, int node) {


if (pq->size == pq->capacity) {
pq->capacity *= 2;
pq->heap = (PQNode*)realloc(pq->heap, pq->capacity * sizeof(PQNode));
}

pq->heap[pq->size] = (PQNode){dist, node};


heapifyUp(pq, pq->size);
pq->size++;
}

PQNode pop(PriorityQueue* pq) {


PQNode top = pq->heap[0];
pq->heap[0] = pq->heap[--pq->size];
heapifyDown(pq, 0);
return top;
}

void dijkstra(Edge** adj, int* adjSize, int N, int src, int dest, int* dist, int*
fromNode) {
for (int i = 0; i < N; i++) {
dist[i] = INT_MAX;
fromNode[i] = -1;
}
dist[src] = 0;
fromNode[src] = src;

PriorityQueue* pq = createPriorityQueue(N);
push(pq, 0, src);

while (pq->size > 0) {


PQNode node = pop(pq);
int u = node.node;
int distance = node.dist;

if (distance > dist[u]) continue;

for (int i = 0; i < adjSize[u]; i++) {


Edge edge = adj[u][i];
int v = (edge.u == u) ? edge.v : edge.u;
int w = edge.w;

if (dist[u] + w < dist[v]) {


dist[v] = dist[u] + w;
push(pq, dist[v], v);
fromNode[v] = u;
}
}
}

free(pq->heap);
free(pq);
}

int main() {
initializeNodeIDs();

int edgeCount;
Edge* edges = getHardcode

You might also like