numNodes = 5; LPpathLengths = 0; While[LPpathLengths < numNodes, ( (* Cycling th
ID: 3698672 • Letter: N
Question
numNodes = 5;
LPpathLengths = 0;
While[LPpathLengths < numNodes,
(
(* Cycling through the short paths of SP *)
For[i = 1, i <= Length[SP], i++,
(
(* We want to append to SP[[i]] the numbers not in SP[[i]].*)
For[j = 2, j <= numNodes, j++,
(
(* See if j is in SP[[i]]. Use counter
k to cycle through SP[[i]]*)
doAppend = True;
For[k = 1, k <= Length[SP[[i]]], k++,
(
If[j == SP[[i, k]] (*OR getCost is too high*),
(
doAppend = False;
Break[];
)];
)]; (* end k loop *)
If[doAppend == True,
(
AppendTo[LP, Append[SP[[i]], j]];
)];
)]; (* end j loop *)
)]; (* end i loop *)
LPpathLengths = Length[ LP[[1]] ];
Print["SP = ", SP];
Print["LP = ", LP];
Print[];
SP = LP;
LP = {};
)]; (* end while loop *)
Print["Final Output = "];
SP
SP = {{1}}
LP = {{1,2},{1,3},{1,4},{1,5}}
SP = {{1,2},{1,3},{1,4},{1,5}}
LP = {{1,2,3},{1,2,4},{1,2,5},{1,3,2},{1,3,4},{1,3,5},{1,4,2},{1,4,3},{1,4,5},{1,5,2},{1,5,3},{1,5,4}}
SP = {{1,2,3},{1,2,4},{1,2,5},{1,3,2},{1,3,4},{1,3,5},{1,4,2},{1,4,3},{1,4,5},{1,5,2},{1,5,3},{1,5,4}}
LP = {{1,2,3,4},{1,2,3,5},{1,2,4,3},{1,2,4,5},{1,2,5,3},{1,2,5,4},{1,3,2,4},{1,3,2,5},{1,3,4,2},{1,3,4,5},{1,3,5,2},{1,3,5,4},{1,4,2,3},{1,4,2,5},{1,4,3,2},{1,4,3,5},{1,4,5,2},{1,4,5,3},{1,5,2,3},{1,5,2,4},{1,5,3,2},{1,5,3,4},{1,5,4,2},{1,5,4,3}}
SP = {{1,2,3,4},{1,2,3,5},{1,2,4,3},{1,2,4,5},{1,2,5,3},{1,2,5,4},{1,3,2,4},{1,3,2,5},{1,3,4,2},{1,3,4,5},{1,3,5,2},{1,3,5,4},{1,4,2,3},{1,4,2,5},{1,4,3,2},{1,4,3,5},{1,4,5,2},{1,4,5,3},{1,5,2,3},{1,5,2,4},{1,5,3,2},{1,5,3,4},{1,5,4,2},{1,5,4,3}}
LP = {{1,2,3,4,5},{1,2,3,5,4},{1,2,4,3,5},{1,2,4,5,3},{1,2,5,3,4},{1,2,5,4,3},{1,3,2,4,5},{1,3,2,5,4},{1,3,4,2,5},{1,3,4,5,2},{1,3,5,2,4},{1,3,5,4,2},{1,4,2,3,5},{1,4,2,5,3},{1,4,3,2,5},{1,4,3,5,2},{1,4,5,2,3},{1,4,5,3,2},{1,5,2,3,4},{1,5,2,4,3},{1,5,3,2,4},{1,5,3,4,2},{1,5,4,2,3},{1,5,4,3,2}}
Final Output =
{{1, 2, 3, 4, 5}, {1, 2, 3, 5, 4}, {1, 2, 4, 3, 5}, {1, 2, 4, 5,
3}, {1, 2, 5, 3, 4}, {1, 2, 5, 4, 3}, {1, 3, 2, 4, 5}, {1, 3, 2, 5,
4}, {1, 3, 4, 2, 5}, {1, 3, 4, 5, 2}, {1, 3, 5, 2, 4}, {1, 3, 5, 4,
2}, {1, 4, 2, 3, 5}, {1, 4, 2, 5, 3}, {1, 4, 3, 2, 5}, {1, 4, 3, 5,
2}, {1, 4, 5, 2, 3}, {1, 4, 5, 3, 2}, {1, 5, 2, 3, 4}, {1, 5, 2, 4,
3}, {1, 5, 3, 2, 4}, {1, 5, 3, 4, 2}, {1, 5, 4, 2, 3}, {1, 5, 4, 3,
2}}
Explanation / Answer
CODE:
#include<iostream>
using namespace std;
int ary[10][10],completed[10],n,cost=0;
void takeInput()
{
int i,j;
cout<<"Enter the number of villages: ";
cin>>n;
cout<<" Enter the Cost Matrix ";
for(i=0;i < n;i++)
{
cout<<" Enter Elements of Row: "<<i+1<<" ";
for( j=0;j < n;j++)
cin>>ary[i][j];
completed[i]=0;
}
cout<<" The cost list is:";
for( i=0;i < n;i++)
{
cout<<" ";
for(j=0;j < n;j++)
cout<<" "<<ary[i][j];
}
}
int least(int c)
{
int i,nc=999;
int min=999,kmin;
for(i=0;i < n;i++)
{
if((ary[c][i]!=0)&&(completed[i]==0))
if(ary[c][i]+ary[i][c] < min)
{
min=ary[i][0]+ary[c][i];
kmin=ary[c][i];
nc=i;
}
}
if(min!=999)
cost+=kmin;
return nc;
}
void mincost(int city)
{
int i,ncity;
completed[city]=1;
cout<<city+1<<"--->";
ncity=least(city);
if(ncity==999)
{
ncity=0;
cout<<ncity+1;
cost+=ary[city][ncity];
return;
}
mincost(ncity);
}
int main()
{
takeInput();
cout<<" The Path is: ";
mincost(0); //passing 0 because starting vertex
cout<<" Minimum cost is "<<cost;
return 0;
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.