Computer Science: 5th sem ADA Lab Program 6

Analysis and Design of Algorithms Lab.

Question 6.

//From a given vertex in a weighted connected graph find shortest paths to other vertices using dijikstra's algorithm

#include <iostream>

#include <conio.h>

#define MAX 10

using namespace std;

void dijkstra(int graph[MAX][MAX], int n,int source)

{

int *vis=new int[n];

int *weight=new int[n];

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

{

vis[i]=0;

weight[i]=graph[source][i];

}

int done=1;

vis[source]=1;

int min_pointer=source;

while(done<=n)

{

int min=99;

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

{

//identify the minimum weighted vertex in the current vertex(not visited earlier).

if(weight[i]<min && vis[i]==0)

{

min=weight[i];

min_pointer=i;//store the minimum weighted vertex

}

}



vis[min_pointer]=1;

done++;

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

{

if(weight[min_pointer]+graph[min_pointer][i]<weight[i] && vis[i]==0)

weight[i]=weight[min_pointer]+graph[min_pointer][i];

}

}

cout<<"\nThe weights are:\n\n";



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

{

cout<<source<<" - "<< i <<" = "<< weight[i]<<" \n";

}

}

void main()

{

cout<<"Enter the number of verticies:";

int n;cin>>n;

cout<<"Enter the weighted matrix:\n";

int graph[MAX][MAX];

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

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

cin>>graph[i][j];

cout<<"Enter the source vertex:";

int source;cin>>source;

dijkstra(graph,n,source);

getch();

}