1. Modify the code in the handout to include memoization. Modify it additionally
ID: 3556807 • Letter: 1
Question
1. Modify the code in the handout to include memoization. Modify it additionally so that it prints the actual shortest path as well as its cost. The path should be output as the sequence of rows to choose, going from left to right on the original cost array. 2. Many dynamic programming problems may be solved quite simply from the bottom up. Write a program to solve the shortest path problem using a bottom up approach. The path should be output as the sequence of rows to choose, going from left to right on the original cost array.
Explanation / Answer
/* PROGRAM TO FIND SHORTEST PATH USING DIJKSTRA'S ALGORITHM THIS IS A STATIC
IMPLEMENTATION OF PROGRAM USING A TWO DIMENTIONAL WEIGHT MATRIX, BUT THIS
PROGRAM CANNOT SUPPORT A SENARIO WHERE NUMBER OF NODES OF A GRAPH MAY
CHANGE DURING EXECUTION */
#include<stdio.h>
#include<conio.h>
#define INFINITY 2000
#define MAXNODES 4
#define MEMBER 1
#define NONMEMBER 0
void shortpath(int weight[][MAXNODES], int , int ,int * ,int precede[]);
int main(void)
{
int i,j,s,t;
int weight[MAXNODES][MAXNODES],precede[MAXNODES],pd;
printf(" Enter weight matrix ");
for(i=0;i<MAXNODES;i++)
for(j=0;j<MAXNODES;j++)
scanf(" %d",&weight[i][j]);
for(i=0;i<MAXNODES;i++)
{
printf(" ");
for(j=0;j<MAXNODES;j++)
printf(" %d",weight[i][j]);
}
printf(" Enter the starting node and the ending node: ");
scanf(" %d %d",&s,&t);
shortpath(weight,s,t,&pd,precede);
printf(" The shortest path from node %d to %d is : %d",s,t,pd);
return(0);
}
void shortpath(int weight[][MAXNODES],int s, int t, int *pd, int precede[])
{
int distance[MAXNODES],perm[MAXNODES];
int current,i,j,k,dc;
int smalldist,newdist;
/* initialization of perm and distance array */
for(i=0;i<MAXNODES;i++)
{
perm[i]=NONMEMBER;
distance[i]=INFINITY;
}
perm[s] = MEMBER;
distance[s] = 0;
current = s;
while(current != t)
{
smalldist=INFINITY;
dc=distance[current];
for(i=0;i<MAXNODES;i++)
if(perm[i]==NONMEMBER)
{
newdist = dc + weight[current][i];
if(newdist < distance[i])
{
distance[i]=newdist;
precede[i]=current;
}
if(distance[i] < smalldist)
{
smalldist = distance[i];
k=i;
}
} /* end of for if */
current = k;
perm[current]=MEMBER;
} /* END WHILE */
*pd=distance[t];
} /* end of shortpath function */
/* END OF PROGRAM */
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.