Lesson 267: The problem of finding the shortest path in Excel

This article will guide you to calculate the short path pressed in Excel.

Find the shortest path

Use solveri in Excel to find the shortest path from node S to node T in an undirected graph. The points in the graph are called nodes (S, A, B, C, D, E and T). The lines in the graph are called arcs (SA, SB, SC, AC, etc.).

Model building

The model we will deal with looks like this in Excel

1. To construct this shortest path problem, we must answer the following three questions.

a. What decisions will be made? For this problem, we need Excel to find if an arc lies on the shortest path (Yes=1, No=0). For example, if SB is part of the shortest path, cell F5 equals 1. Otherwise, cell F5 equals 0.

b. What are the constraints on these decisions? The Net Flow (Net Flow) of each node must equal Supply/Demand. Node S should have only one egress arc (Net Flow = 1). Node T should have only one running arc (Net Flow = -1). All other nodes must have an egress and an ingress arc if the node is on the shortest path (Net Flow=0) or no flow (Net Flow=0).

c. What are the overall performance metrics for these decisions? The overall metric of performance is the total distance of the shortest path, so the goal is to minimize this quantity.

2. To make the model easier to understand

3. Add function

Trial and error

1. For example, the SBET path has a total distance of 16.

Solve the model

1. On the Data panel select Solver

Enter the parameters. The result should match the figure below.

2. Import TotalDistance for Objective.

3. Click Min.

4. Enter Go for Changing Variable Cells.

5. Click Add

6. Select ‘Make Unconstrained Variables Non-Negative’ and select ‘Simplex LP’.

7. Finally click Solve.

Result

Optimal solution:

Conclusion: SADCT is the shortest path with a total distance of 11.

In addition, you can also view many other excel articles here.