Answer:
a)
Algorithm to find a solution of min. cost
Function:cost(Graph G,Graph G1);
GC --> empty graph
for i in edges E:
if E(i,j) in G:
c(i,j)=c(i,j)
else if E(i,j) in G1:
c(i,j)=-c(i,j)
Function:Mincost(Graph G):
GC=Cost(G,G1)
while(negativecycle(GC)):
Update residal graph(G1)
GC=Cost(G,G1)
mincost=sum of Cij*F(i,j)
return mincost;
Explanation:
a)
1) Start the program
2) Read the no. of edges and vertices and also read the cost of the two nodes.
3) Find the min cost by travelling to the destination i.e.. finding all possible min. cost values.
4) Compare the all possible min.cost values
5) And display the least min. cost
6) Stop the program
b)
<u>Correctness of algorithm</u>
1)Here in these algorithm we are calculating all the possible cases.
2)These algorithm also supports the negative cost.
3)These algorithm occupies more space.
4)Takes less time
5)so,these algorithm provides the cost efficient solution very effectively.
c)
<u>Run Time Analysis</u>
1) While reading the values during the run time the program execution will stop until user provides the values.
2) Based on the User input Output vary.
3) Time consumption and space consumption is depends on the no. of inputs the user is given.
