t H e — C o M p L e T e — I n F o


      

DYNAMIC PROGRAMMING PRESENTATION

Matrix Chain Multiplication PRESENTATION

Write a program to find the all pairs shortest path for a given graph

#include<iostream.h> #include<conio.h> #include<stdlib.h> int cost[10][10],i,j,k,n,stk[10],top,v,visit[10],visited[10],u; void main() { clrscr(); int m,c; cout <<"enterno of vertices"; cin >> n; cout <<"ente no of edges"; cin >> m; cout <<"\nEDGES Cost\n"; for(k=1;k<=m;k++) { cin >>i>>j>>c; cost[i][j]=c; } for(i=1;i<=n;i++) for(j=1;j<=n;j++) if(cost[i][j]==0) cost[i][j]=31999; cout<<”\n*****prim’s algorithm*****”; cout <<"\nORDER OF VISITED VERTICES"; k=1; while(k<n) { m=31999; if(k==1) { for(i=1;i<=n;i++) for(j=1;j<=m;j++) if(cost[i][j]<m) […]

Write a program to find the shortest distance from the source node to every other node

#include<iostream.h> #include<conio.h> #include<stdlib.h> int cost[10][10],i,j,k,n,stk[10],top,v,visit[10],visited[10],u; void main() { clrscr(); int m,c; cout <<"enterno of vertices"; cin >> n; cout <<"ente no of edges"; cin >> m; cout <<"\nEDGES Cost\n"; for(k=1;k<=m;k++) { cin >>i>>j>>c; cost[i][j]=c; } for(i=1;i<=n;i++) for(j=1;j<=n;j++) if(cost[i][j]==0) cost[i][j]=31999; cout<<”\n*****prim’s algorithm*****”; cout <<"\nORDER OF VISITED VERTICES"; k=1; while(k<n) { m=31999; if(k==1) { for(i=1;i<=n;i++) for(j=1;j<=m;j++) if(cost[i][j]<m) […]

Write a program to construct a MST (Minimum Spanning Tree) using Kruskal Algorithm

#include<iostream.h> #include<conio.h> #include<stdlib.h> int cost[10][10],i,j,k,n,m,c,visit,visited[10],l,v,count,count1,vst,p; void main() { clrscr(); int dup1,dup2; cout<<"enter no of vertices"; cin >> n; cout <<"enter no of edges"; cin >>m; cout <<"EDGE Cost"; for(k=1;k<=m;k++) { cin >>i >>j >>c; cost[i][j]=c; cost[j][i]=c; } for(i=1;i<=n;i++) for(j=1;j<=n;j++) if(cost[i][j]==0) cost[i][j]=31999; visit=1; while(visit<n) { v=31999; for(i=1;i<=n;i++) for(j=1;j<=n;j++) if(cost[i][j]!=31999 && cost[i][j]<v && cost[i][j]!=-1 ) { int […]

Write a program to construct a MST (Minimum Spanning Tree) using Prims Algorithm.

#include<iostream.h> #include<conio.h> #include<stdlib.h> int cost[10][10],i,j,k,n,stk[10],top,v,visit[10],visited[10],u; void main() { clrscr(); int m,c; cout <<"enterno of vertices"; cin >> n; cout <<"ente no of edges"; cin >> m; cout <<"\nEDGES Cost\n"; for(k=1;k<=m;k++) { cin >>i>>j>>c; cost[i][j]=c; } for(i=1;i<=n;i++) for(j=1;j<=n;j++) if(cost[i][j]==0) cost[i][j]=31999; cout<<”\n*****prim’s algorithm*****”; cout <<"\nORDER OF VISITED VERTICES"; k=1; while(k<n) { m=31999; if(k==1) { for(i=1;i<=n;i++) for(j=1;j<=m;j++) if(cost[i][j]<m) […]

Write a program to solve the travelling salesman problem

//Travelling Salesman problem #include <iostream.h> #include <conio.h> class dynamic { private: int c[5][5],n,d[24],p[24][6],list[5],r,i,j; public: dynamic(); void getdata(); void display(); int fact(int num); int min(int list[]); void perm(int list[], int k, int m); void sol(); }; dynamic::dynamic() { r=0; } void dynamic::getdata() { cout<<"Enter no. of cities:"; cin>>n; cout<<endl; for (int i=0;i<n;i++) for (int j=0;j<n;j++) c[i][j]=0; […]

a program to traverse a graph using Depth First Search Algorithm

#include<iostream.h> #include<conio.h> #include<stdlib.h> int cost[10][10],i,j,k,n,stk[10],top,v,visit[10],visited[10]; void main() { int m; cout <<"enterno of vertices"; cin >> n; cout <<"ente no of edges"; cin >> m; cout <<"\nEDGES \n"; for(k=1;k<=m;k++) { cin >>i>>j; cost[i][j]=1; } cout <<"enter initial vertex"; cin >>v; cout <<"ORDER OF VISITED VERTICES"; cout << v <<" "; visited[v]=1; k=1; while(k<n) { for(j=n;j>=1;j–) […]

Write a program to traverse a graph using Breadth First Search Algo rithm.

#include<iostream.h> #include<conio.h> #include<stdlib.h> using namespace std; int cost[10][10],i,j,k,n,qu[10],front,rare,v,visit[10],visited[10]; main() { int m; cout <<"enterno of vertices"; cin >> n; cout <<"ente no of edges"; cin >> m; cout <<"\nEDGES \n"; for(k=1;k<=m;k++) { cin >>i>>j; cost[i][j]=1; } cout <<"enter initial vertex"; cin >>v; cout <<"Visitied vertices\n"; cout << v; visited[v]=1; k=1; while(k<n) { for(j=1;j<=n;j++) if(cost[v][j]!=0 && […]

Previous Posts