473,322 Members | 1,620 Online
Bytes | Software Development & Data Engineering Community
Post Job

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 473,322 software developers and data experts.

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 4842
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

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

Similar topics

3
by: Dan | last post by:
I am a relatively new user on Oracle 9.2.0.1 and I am having trouble performance tuning this production database. I am running a large query that joins two tables, document(3 mil) and entity(9...
8
by: Agoston Bejo | last post by:
Take a look at the following example: table T(i INTEGER, j INTEGER) I want to get the value of i where j is minimal and some conditions apply. (1) SELECT i FROM T WHERE AND j
6
by: ThanhVu Nguyen | last post by:
Hi all, I need recommendation for a very fast shortest path algorithm. The edges are all directed, positive weights. Dijkstra shortest path will solve it just fine but the if the graph is not...
20
by: Webdad | last post by:
Hi! I running my first year as industrial engineer (informatics) We have an assignment to do : .... create a playfield (matrix). Some places in that field are blocked, so you can't pass them....
2
by: tonokio | last post by:
I wasn't sure if this was the best place to post since there isn't really an algorithm section for programming. I was curious that if you're given a MST tree of G and P is the shortest path between...
6
by: finerrecliner | last post by:
hey everyone i'm trying to make a function that will return the length and width of a dynamically allocated 2D array. here's what i came up with to find width: int findWidth(int** matrix)...
1
by: elissa | last post by:
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:...
9
by: curiously enough | last post by:
I need a practical method to find the eigenvalues of a matrix in C++ because the one I know(the only one I know) is to subtract the elements of the diagonal by the eigenvalue and then find the...
7
by: latalui | last post by:
i am a beginner, guys plizzzzzzzz help me. i am given a assignment to find short paths either using dijkstra algorithm or using binary search algorithm in linux OS. check out what is wrong the code...
0
by: DolphinDB | last post by:
Tired of spending countless mintues downsampling your data? Look no further! In this article, you’ll learn how to efficiently downsample 6.48 billion high-frequency records to 61 million...
0
by: ryjfgjl | last post by:
ExcelToDatabase: batch import excel into database automatically...
1
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 6 Mar 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). In this month's session, we are pleased to welcome back...
0
by: jfyes | last post by:
As a hardware engineer, after seeing that CEIWEI recently released a new tool for Modbus RTU Over TCP/UDP filtering and monitoring, I actively went to its official website to take a look. It turned...
1
by: Defcon1945 | last post by:
I'm trying to learn Python using Pycharm but import shutil doesn't work
1
by: Shællîpôpï 09 | last post by:
If u are using a keypad phone, how do u turn on JavaScript, to access features like WhatsApp, Facebook, Instagram....
0
by: af34tf | last post by:
Hi Guys, I have a domain whose name is BytesLimited.com, and I want to sell it. Does anyone know about platforms that allow me to list my domain in auction for free. Thank you
0
by: Faith0G | last post by:
I am starting a new it consulting business and it's been a while since I setup a new website. Is wordpress still the best web based software for hosting a 5 page website? The webpages will be...
0
isladogs
by: isladogs | last post by:
The next Access Europe User Group meeting will be on Wednesday 3 Apr 2024 starting at 18:00 UK time (6PM UTC+1) and finishing by 19:30 (7.30PM). In this session, we are pleased to welcome former...

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.