Category Archives: Graphs

INDEX


1)BELLMAN FORD’S SINGLE SOURCE SHORTEST PATH ALGORITHM

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

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

4)Depth First Search algorithm in general terms

5) Breadth First Search algorithm in general terms

6)general algorithm for prim’s minimum spanning tree

7)general algorithm for kruskal’s minimum spanning tree

8)Breadth First Search

9)Kruskal’s Algorithm for Minimum Spanning Tree

10)Depth First Search

11)Prim’s Algorithm for Minimum Spanning tree

12)Topological Sorting

13)Code For Dijkstra’s Algorithm In C

14)Shortest Path Problem

15)Code For Dijkstra’s Algorithm In C++

Advertisements

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:
        Graph :: Adjacency matrix

  -> Header files 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 read_graph();
 void initialize();
 void update();
 void check();
 void algorithm();
};

void bell_ford::read_graph()
{
 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()
{
 read_graph();
 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:
        Graph :: Adjacency matrix

  -> Header files 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 read_graph();
 void initialize();
 int select_min_distance_lable();
 void update(int);
 void output();
 void function();
};

void dijkstra::read_graph()
{
 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”;
 read_graph();
 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.