I have been given a large data set with a list of starting nodes, their destination nodes, and the length to each destination node from each starting node. Using Dijkstra's algorithm, I coded a shortest path problem for the data set, but now I am being asked "what is the reduced cost of the flow variable $x_{1, 72}$ where the length between nodes 1 and 72 is 21.
How do I found what the reduced cost is and what does it mean? I thought the reduced cost would be 21 since that is the cost that the path increases by by going through those two nodes, but I don't think that is right. How does the optimal value change if we change the length between those nodes to 10 instead?
Let $c_{ij}$ be the original arc cost of variable $x_{ij}$, and let $\pi_i$ be the dual variable for node $i$. The reduced cost of variable $x_{ij}$ is $c_{ij}-\pi_i+\pi_j$. The interpretation is that (assuming nondegeneracy) the reduced cost is the amount of improvement in the objective value per unit decrease of $c_{ij}$ if all other arc costs stay the same.