Project Description

Algorithm Design

Source Code

Output(Screen Shots)

Result Analysis

Data Structure Project 4: Dijkstras Algorithm

Dijkstras Algorithm provides a very effective solution for finding shortest path from a source node to all the other nodes. Please write a program in C language to implement this algorithm.

Source Code for Reference

// Program of shortest paths from a source node to all other nodes

// in a weighted graph using Dijkstra's Algorithm

#include

// #define N 6

#define N 9

#define Infinity 0x7fffffff

void Dijkstra(int n, int adjMatrix[][N], int source, int prev[], int dist[]);

void printShortestPath(int dest, int source, int prev[N], int dist[N]);

int main()

{ int source=0;

/*int adjMatrix[N][N] = {

0, 6, 5, 0, 0, 0,

0, 0, 5, 0, 3, 2,

0, 0, 0, 2, 0, 3,

0, 0, 0, 0, 0, 1,

0, 0, 0, 4, 0, 0,

0, 0, 0, 0, 3, 0

};*/

int adjMatrix[N][N] = {

0,36, 1,15, 0, 0, 0, 0, 0,

0, 0, 0, 0, 0, 0,14, 0, 0,

0,33, 0,11,31, 0, 0, 0, 0,

0, 0, 0, 0, 0, 8, 0, 0, 0,

0, 7, 0, 0, 0, 0,12, 0, 0,

0, 0, 9, 0,10, 0, 0, 5, 0,

0, 0, 0, 0, 0, 0, 0, 0,13,

0, 0, 0, 0, 3, 0,16, 0,30,

0, 0, 0, 0, 0, 0, 0, 0, 0

};

int prev[N], dist[N];

Dijkstra(N, adjMatrix, source, prev, dist);

}

void Dijkstra(int n, int adjMatrix[N][N], int source, int prev[N], int dist[N])

{ int i,j,minWeight,minID,temp,finish[N];

for(i=0; i

finish[i]=0;

prev[i]=(adjMatrix[source][i]!=0)?source:-1;

dist[i]=(adjMatrix[source][i]!=0)?adjMatrix[source][i]:Infinity;

}

finish[source]=1;

dist[source]=0;

for(i=1; i

minWeight=Infinity;

for(j=0; j

if(finish[j]!=1 && dist[j]

minWeight=dist[j];

minID=j;

}

}

finish[minID]=1;

printShortestPath(minID, source, prev, dist);

for (j=0; j

if(adjMatrix[minID][j]==0) continue;

temp = minWeight + adjMatrix[minID][j];

if(finish[j]==0 && temp

dist[j]=temp;

prev[j]=minID;

}

}

}

}

void printShortestPath(int dest, int source, int prev[], int dist[])

{ int pred;

printf("The shortest path from %c to %c is: ", source+65, dest+65);

pred=dest;

do {

printf("%c

pred=prev[pred];

} while(pred!=source);

printf("%c , distance is %d ", source+65, dist[dest]);

}

Experiment Requirements

1. Record the output of the programs(screen shots)

2. Analyze the output results

Test Graphs 14 (A (B (G | 6 5 36 7 13 5 33 B C 12 2 3 31 C E 16 3 N 3 3 1 11 9 3 15 10 30 E 4 H 8 5