# BELLMAN FORD’S SINGLE SOURCE SHORTEST PATH ALGORITHM

/*************************************************************************

-> This C++ program is to implement Bellmen Ford algorithm.

-> Bellmen Ford algorithm solves the single source shortest paths
problem in the general case in which edge weights may be negative.

-> This algorithm returns true if the graph contains no
negative-weight cycles that are reachable from the source
else returns the shortest paths from the source.

-> This program works in Microsoft VC++ environment in windows xp

-> Data structures used:

1)iostream.h
2)stdlib.h

/*************************************************************************/

#include<iostream.h>
#include<stdlib.h>

#define MAX 20
#define INFINITY 9999

class bell_ford
{
private:
int n;
int graph[MAX][MAX];
int start;
int distance[MAX];
int predecessor[MAX];
public:
void initialize();
void update();
void check();
void algorithm();
};

{
cout<<“Enter the no. of nodes in the graph ::”;
cin>>n;
cout<<“Enter the adjacency matrix for the graph ::\n”;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
cin>>graph[i][j];
cout<<“Enter the start vertex ::”;
cin>>start;
}

void bell_ford::initialize()
{
for(int i=1;i<=n;i++)
{
distance[i]=INFINITY;
predecessor[i]=0;
}
distance[start]=0;
}

void bell_ford::update()
{
for(int i=1;i<=n-1;i++)
{
for(int u=1;u<=n;u++)
{
for(int v=1;v<=n;v++)
{
if(graph[u][v]!=0)
{
if(distance[v]>distance[u]+graph[u][v])
{
distance[v]=distance[u]+graph[u][v];
predecessor[v]=u;
}
}
}
}
}
}

void bell_ford::check()
{
for(int u=1;u<=n;u++)
{
for(int v=1;v<=n;v++)
{
if(graph[u][v]!=0)
{
if(distance[v]>distance[u]+graph[u][v])
{
cout<<“does not exist’s “;
return;
}
}
}
}

cout<<“\n\nThere is no negative weight cycle and\n”;
cout<<“****** The final paths and the distacnes are ******\n\n”;
for(int i=1;i<=n;i++)
{
cout<<“path for node “<<i<<” is ::\n”;
int arr[MAX],k=1;
int j=i;
while(predecessor[j]!=0)
{
arr[k]=predecessor[j];
k++;
j=predecessor[j];
}
for(–k;k>0;k–)
cout<<arr[k]<<“->”;
cout<<i<<endl;
cout<<“distance is “<<distance[i]<<endl<<endl<<endl;
}
}

void bell_ford::algorithm()
{
initialize();
update();
check();
}

void main()
{
bell_ford obj;
obj.algorithm();
}

# CODE-2 FOR DIJKSTRA’S SHORTEST PATH ALGORITHM IN C++

/*************************************************************************

-> This C++ program is to implement Dijkstra’s algorithm for
single source shortest path problem

-> This program works in Microsoft VC++ environment in windows xp

-> Data structures used:

1)iostream.h
2)stdlib.h

/*************************************************************************/
#include<iostream.h>
#include<stdlib.h>

#define MAX 20
#define INFINITY 9999

class dijkstra
{
private:
int n;
int graph[MAX][MAX];
int colour[MAX];
int start;
int distance[MAX];
int predecessor[MAX];
enum {green,yellow,red};
public:
void initialize();
int select_min_distance_lable();
void update(int);
void output();
void function();
};

{
cout<<“Enter the no. of nodes in the graph ::”;
cin>>n;
cout<<“Enter the adjacency matrix for the graph ::\n”;
int i,j;
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
cin>>graph[i][j];
for(i=1;i<=n;i++)
colour[i]=green;

cout<<“Enter the start vertex ::”;
cin>>start;
}

void dijkstra::initialize()
{
for(int i=1;i<=n;i++)
{
if(i==start)
distance[i]=0;
else
distance[i]=INFINITY;
}

for(int j=1;j<=n;j++)
{
if(graph[start][j]!=0)
predecessor[j]=start;
else
predecessor[j]=0;
}
}

int dijkstra::select_min_distance_lable()
{
int min=INFINITY;
int p=0;
for(int i=1;i<=n;i++)
{
if(colour[i]==green)
{
if(min>=distance[i])
{
min=distance[i];
p=i;
}
}
}
return  p;
}

void dijkstra::update(int p)       // p is a yellow colour node
{
cout<<“\nupdated distances are ::\n”;
for(int i=1;i<=n;i++)
{
if(colour[i]==green)
{
if(graph[p][i]!=0)
{
if(distance[i]>graph[p][i]+distance[p])
{
distance[i]=graph[p][i]+distance[p];
predecessor[i]=p;
}
}
}
cout<<distance[i]<<‘\t’;
}
}

void dijkstra::output()
{
cout<<“****** The final paths and the distacnes are ******\n\n”;

for(int i=1;i<=n;i++)
{
if(predecessor[i]==0 && i!=start)
{
cout<<“path does not exists between “<<i<<” and the start vertex ”
<<start<<endl;
exit(1);
}
cout<<“path for node “<<i<<” is ::\n”;
int j=i;
int array[MAX];
int l=0;
while(predecessor[j]!=0)
{
array[++l]=predecessor[j];
j=predecessor[j];
}
for(int k=l;k>=1;k–)
cout<<array[k]<<“->”;

cout<<i<<endl;
cout<<“distance is “<<distance[i]<<endl<<endl<<endl;
}
}

void dijkstra::function()
{
cout<<“\n**********************************************************************\n”;
cout<<“This program is to implement dijkstra’s algorithm using colour codes \n”;
cout<<“**********************************************************************\n\n”;
initialize();
//repeate until all nodes become red
int flag=0;
int i;

cout<<“\n\n******** The working of the algorithm is **********\n\n”;

for(i=1;i<=n;i++)
if(colour[i]!=red)
flag=1;

cout<<“The initial distances are ::\n”;
for(i=1;i<=n;i++)
cout<<distance[i]<<‘\t’;
cout<<endl;

while(flag)
{
int p=select_min_distance_lable();
cout<<“\nThe min distance lable that is coloured yellow is “<<p;
colour[p]=yellow;

update(p);
cout<<“\nnode “<<p<<” is coloured red “<<endl;
colour[p]=red;

flag=0;
for(i=1;i<=n;i++)
if(colour[i]!=red)
flag=1;

cout<<endl<<endl<<endl;
}
output();
}

void main()
{
dijkstra d;
d.function();
}

# A general algorithm to implement Dijkstra’s solution for single source shorest path problem

*********************************************************

Input :
Adjacency list representation of graph – a [ ][ ]
A source vertex – s
Output :
distance array – d [ ]

(An array named parent array is used to store the parent node for each node in the final tree structure derived which consists of shotests paths.)

***********************************************************

ALGORITHM:

1) Initialize d[i]=a[s][i] , 1 ≤ i ≤ n.
Set p[i]=s for all i adjacent from s. Set p[i] = 0 for all other vertices.
Create a list L of all vertices for which p[i] ≠ 0.

2)While L is not empty repeate through steps 3 and 4

3)Delete from L the vertex i with least value of d (ties are broken arbritrarily).

4) Up date d[j] to minimum of { d[j] , d[i]+a[i][j] } for all unreached vertices j adjacent from i. If d[j] changes , set p[j] =i , and add j to L in case it is not already there.

# Depth First Search algorithm in general terms

************************************************

Input :
Un weighted graph
Beginning vertex -v
Output :
The visited vertices.
Data structures used :Stack to store the vertices
************************************************

ALGORITHM:

1)Lable vertex v as reached.
2)Initialize S to be a stack with only v in it.
3)while S is not empty repeate through steps 4 , 5 & 6.
4)Delete a vertex w from the stack.
5)for all vertices u adjacent from w repeate through steps 6.
6)if u has not been labeled add u to the stack S , lable u as reached.

# Breadth First Search algorithm in general terms

****************************************************

Input :
Un weighted graph
Beginning vertex -v
Output :
The visited vertices.
Data structures used :Queue to store the vertices
****************************************************

ALGORITHM:

1)Lable vertex v as reached.
2)Initialize Q to be a queue with only v in it.
3)while Q is not empty repeate through steps 4 , 5 & 6.
4)Delete a vertex w from the queue.
5)for all vertices u adjacent from w repeate through steps 6.
6)if u has not been labeled add u to the queue Q , lable u as reached.

# general algorithm for prim’s minimum spanning tree

Prim’s algorithm (in general terms) for minimum spanning tree
*************************************************************

1.Let T be the set of edges in the minimum spanning tree.

2.Initialize T=Ø.

3.Let TV be the set of vertices in the tree.

4.Initialize TV={1}.

5.Let E be the set of graph edges.

6.Repeat through steps 7,8,9,10 while E≠Ø and |T|≠n-1.

7.Let(u,v)be the least cost edge such that u is in TV and v is not in TV.

8.if There is no such edge go to step 11.

9.E=E-{(u,v)} i.e. delete the edge from E.

10.Add the edge (u,v) to T.

11.If(|T|=n-1) T is a minimum cost spanning tree else the network is not

connected and has no spanning tree.