Scribd
Upload
6 views3 pages

Dijkstra's Algorithm in C Code

The document contains a C program that implements Dijkstra's algorithm to find the shortest paths from a starting vertex in a graph represented by an adjacency matrix. It initializes the cost matrix, calculates distances, and displays the results for each vertex. The program prompts the user for the number of vertices, the adjacency matrix, and the starting node before executing the algorithm.

Uploaded by

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

Dijkstra's Algorithm in C Code

The document contains a C program that implements Dijkstra's algorithm to find the shortest paths from a starting vertex in a graph represented by an adjacency matrix. It initializes the cost matrix, calculates distances, and displays the results for each vertex. The program prompts the user for the number of vertices, the adjacency matrix, and the starting node before executing the algorithm.

Uploaded by

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

#include <stdio.

h>

#define INF 9999

#define MAX 10

void dijkstra(int G[MAX][MAX], int n, int start) {

int cost[MAX][MAX], dist[MAX], visited[MAX], parent[MAX];

int count, mindist, next, i, j;

// Create cost matrix

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

for (j = 0; j < n; j++)

cost[i][j] = (G[i][j] == 0) ? INF : G[i][j];

// Initialize

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

dist[i] = cost[start][i];

parent[i] = (cost[start][i] != INF && i != start) ? start : -1;

visited[i] = 0;

dist[start] = 0;

visited[start] = 1;

count = 1;

// Dijkstra's main loop

while (count < n - 1) {

mindist = INF;

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

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

mindist = dist[i];

next = i;

}
visited[next] = 1;

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

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

dist[i] = mindist + cost[next][i];

parent[i] = next;

count++;

// Display results

printf("\nVertex\tDistance from %d\n", start);

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

if (i != start)

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

int main() {

int G[MAX][MAX], n, start;

printf("Enter number of vertices: ");

scanf("%d", &n);

printf("Enter adjacency matrix:\n");

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

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

scanf("%d", &G[i][j]);

printf("Enter starting node: ");

scanf("%d", &start);

dijkstra(G, n, start);

return 0;

}
Sample Output :-

Enter number of vertices: 3

Enter adjacency matrix:

023

207

370

Enter starting node: 2

Vertex Distance from 2

2 -> 0 3

2 -> 1 5

You might also like