 Hey guys, I'm really stuck on this problem. I think you have to do backward recursion, but don't know how to go about it. I just need help with the algorthim for the function "backtracking".

Find the best cheapest way to get from city 1 to city 2. I have already found the cheapest way by hand, which city1 -> city 2 -> city 5 -> city 8 -> city 10. Here is a picture of the diagram ^

Here is the code I have so far.

#include <stdio.h>

int backTracking(not sure what to put here..)
{
//.....
}

}
int main (void)
{
//hard code all the prices
int cityOneTwo = 2;
int cityOneThree = 5;
int cityOneFour=3;
int cityTwoFive=3;
int cityTwoSix=6;
int cityThreeFive=7;
int cityThreeSix=8;
int cityFourSix= 10;
int cityFourFive=4;
int cityFiveEight=2;
int cityFiveSeven=3;
int citySixSeven=4;
int citySixEight=2;
int citySixNine= 5;

int cost; //make an array for day and city... day 1 includes city 1, day 2 includes city 2,3,4... and so on

//day 4
cost=7; //intiallize cost from city 7 to city 10
cost=6; //intiallize cost from city 8 to city 10
cost=5; //intiallize cost from city 9 to city 10

//day 3: city 5
int wayFiveSeven=cityFiveSeven + cost;
int wayFiveEight= cityFiveEight + cost;

if (wayFiveSeven<wayFiveEight)
cost = wayFiveSeven;
else
cost = wayFiveEight;

//day 3: city 6
int waySixSeven= citySixSeven + cost;
int waySixEight= citySixEight + cost;
int waySixNine= citySixNine + cost;

if (waySixSeven < waySixEight && waySixSeven <waySixNine)
cost= waySixSeven;
else if (waySixEight < waySixSeven && waySixEight < waySixNine)
cost = waySixEight;
else
cost = waySixNine;

//day 2: city 4
int wayFourFive = cityFourFive + cost;
int wayFourSix= cityFourSix + cost;

if (wayFourFive<=wayFourSix)
cost= wayFourFive;
else
cost= wayFourSix;

//day 2: city 3

int wayThreeFive = cityThreeFive + cost;
int wayThreeSix = cityThreeSix + cost;

if (wayThreeFive <= wayThreeSix)
cost= wayThreeFive;
else
cost= wayThreeSix;

//day 2: city 2
int wayTwoFive= cityTwoFive + cost;
int wayTwoSix= cityTwoSix + cost;

if (wayTwoFive <= wayTwoSix)
cost= wayTwoFive;
else
cost= wayTwoSix;

//day 1: city 1

int wayOneTwo = cityOneTwo + cost;
int wayOneThree = cityOneThree + cost;
int wayOneFour = cityOneFour + cost;

if (wayOneTwo < wayOneThree && wayOneTwo < wayOneFour)
cost= wayOneTwo;
else if (wayOneThree < wayOneTwo && wayOneThree < wayOneFour)
cost = wayOneThree;
else
cost = wayOneFour;

//determine the total cost

int totalcost= backTracking(not sure what to put here...);
} forgot to put return (0); between line 100 and line 101.

p.s its a backward dynamic program.

Dynamic programming most times revolves around caching or memoization generally coupled with some sort of recursion. The idea in this case would look something like:

for each Node1 in Graph:
set Node1 as Root.
for each Node2 in (Graph - Node1):
calculate ShortestPath(Root, Node2)

print ShortestPath(NodeA, NodeB)


The ShortestPath would be the recursive portion that would do the caching

ShortestPath(Root,Target)

if exists CACHE[(Root,Target)]
return CACHE[(Root,Target)]

LowestCost = Infinity

for Neighbor in Root.Neighbors:
Cost = Cost(Root,Neighbor) + ShortestPath(Neighbor,Target)
if Cost < LowestCost
LowestCost = Cost

CACHE[(Root,Target)] = LowestCost
return LowestCost


The first iteration is the most costly as every call to ShortestPath requires you to do the full calculation. As you iterate over the nodes the cache fills up and by the last few nodes you have to do very little calculation since you've already traversed the entire graph.