In this post, you’ll learn what is shortest path problem and how to solve a shortest path problem in Excel using the solver tool.
Shortest Path Problem
As the name says this problem is about finding the shortest path between two points or destinations comparatively, which minimizes the cost of transportation or production.
Lets look at a example of this problem. Look at the screenshot attached below.
A problem has been framed, the diagram gives us the map of the transportation and the cost units required to reach destinations. We are required to find the path which will cost us the least.
In the solution space, the outgoing is the sum of the respective rows similarly the Incoming is the sum of the respective columns. And the Out-In is the difference between the Out and In accordingly to its column and row.
RHS is the condition for the nodes that go out from that point, since Z is the starting position it’s assigned to 1, similarly to the other points.
The Optimal solution is the sum and product of the given values and the changing variables, so use the formula =SUMPRODUCT().
Shortest Path Problem Using Excel Solver
- Go to the Data tab and under Analyze group select the Solver tool.
- When the Solver parameters dialog box opens up, set the objective to Min. By changing variables are the variables in the Solution space.
- Subject to the constraints are Out-In = RHS and the Changing variables are Binary numbers.
- The solving method is Simplex LP.
- After making all the changes click on Solve.
When the Solver results dialog box opens up, click on Keep the Solver solution< OK and the solution gets displayed.
This is how you find the shortest path in a problem in Excel using Solver tool.
