470,815 Members | 1,204 Online
Bytes | Developer Community
New Post

Home Posts Topics Members FAQ

Post your question to a community of 470,815 developers. It's quick & easy.

how to find the minimum cost path in a matrix

3
hi guys i really wish if some one could help me with this problem , well i solved it but the output is always wrong so can some one help me:

the Question is in this link:
http://people.westminstercollege.edu/faculty/ggagne/fall2006/306/handouts/hw2/index.html

can some one please help me with the dynamic programing part of the question
this is what i did so far:
---------------------------------
#include <iostream>
using namespace::std;

const int q1=4;
const int q2=4;
double Array[q1][q2]={16,5,4,6,2,5,1,9,8,7,6,5,4,3,2,1};//global variable
double Array2[q1][q2]={16,5,4,6,2,5,1,9,8,7,6,5,4,3,2,1};
//-------Class Object----------
class Object
{
public:
double cost;
int i,j;
};
//-------------------------------

//-----------fuction smallest , return the value of smallest element-------
double smalest(Object A,Object B,Object C)
{

double min;

min=A.cost;
Array2[A.i][A.j]=-1;


if(min>B.cost)
{ Array2[A.i][A.j]=Array[A.i][A.j];
min=B.cost;
Array2[B.i][B.j]=-1;

}

if(min>C.cost)
{ cout<<"in C loop "<<min<<"\n";
Array2[B.i][B.j]=Array[B.i][B.j];
Array2[A.i][A.j]=Array[A.i][A.j];
min=C.cost;
Array2[C.i][C.j]=-1;

}

return min;
}
//---------------------------------------------------------------------------

//------------------function shortest find the shortest path ---------------

Object shortest(int i,int j,int Jmax)
{

if(j>Jmax || i<0 ||i>=q1 )
{Object noValue;
noValue.cost=100000;
return noValue;
}

if(j==Jmax)
{Object temp;
temp.cost=Array[i][j];
temp.i=i;
temp.j=j;
return temp;
}

else
{
Object value;
value.cost= smalest(shortest(i,j+1,Jmax),shortest(i+1,j+1,Jmax ),shortest(i-1,j+1,Jmax))+Array[i][j];
value.i=i;
value.j=j;
return value;}

}

//--------------------------------------------------------------------------------

int main()
{
Object cost;
cost =shortest(1,0,3);

cout<<cost.cost<<"\n";

for (int i=0;i<q1;i++)
{
for (int j=0;j<q2;j++)
cout<<Array2[i][j]<<" ";
cout<<"\n";
}

cout<<"\n";
for ( i=0;i<q1;i++)
{
for (int j=0;j<q2;j++)
cout<<Array[i][j]<<" ";
cout<<"\n";
}

return 0;}
-----------------------------

i hope some one could help me or just post the algorithem
thank all , i will appreciates any attempt
Apr 30 '07 #1
2 4639
JosAH
11,448 Expert 8TB
Have a look at the Floyd Warshall algorithm.

kind regards,

Jos
Apr 30 '07 #2
elissa
3
thanks for your replay
but i stell dont get it

how can i modify my code to find the correct min path
should i use link list or tree ?
i dont know
May 1 '07 #3

Post your reply

Sign in to post your reply or Sign up for a free account.

Similar topics

3 posts views Thread by Dan | last post: by
8 posts views Thread by Agoston Bejo | last post: by
6 posts views Thread by ThanhVu Nguyen | last post: by
2 posts views Thread by tonokio | last post: by
6 posts views Thread by finerrecliner | last post: by
7 posts views Thread by latalui | last post: by
By using this site, you agree to our Privacy Policy and Terms of Use.