#C_{i,j} matrix provided as an input

C = [0 1 2 0 0 0 0 0 0;

0 0 0 6 12 0 0 0 0;

0 0 0 3 0 4 0 0 0;

0 0 0 0 4 3 15 7 0;

0 0 0 0 0 0 7 0 0;

0 0 0 0 0 0 0 7 15;

0 0 0 0 0 0 0 0 3;

0 0 0 0 0 0 0 0 10;

0 0 0 0 0 0 0 0 0;

]

#Definitions

n = size(C,1) #total number of nodes

f = zeros(n)  #array to store final f values

temp = zeros(n,n) #temp matrix to store C[i,j] + f[j]


#Initialize last state to be 0 for backward recursion

f[n] = 0

#For loop - for calculating the value of the states (f)

for i = n-1:-1:1

    for j = 1:n

        if (C[i,j]>0)

            temp[i,j] = C[i,j]+f[j]

        else

            temp[i,j] = 500

        end

    end

    f[i] = minimum(temp[i,:])#pick the minimum value (min prob)

end


#Output value of states (f)

f

#Shortest path is the value of the first state f[1]
f[1]

#Calculate the optimal path going forward

path = Int64[]
push!(path,1) #Starting from node 1

i = 1

while i < n

    for j = 1:n
        
        if f[i] == temp[i,j]
        
            push!(path,j)
            i = j
        
        end

    end

end


#Print the optimal path
path