Course 6 : Shortest path problem

Author: OptimizationCity Group

Table of Contents

Introduction

So far, we have studied the problem of linear programming in general. In this section, we will examine specific types of linear programming problems. In this section, we first examined the general model of minimum cost flow, and then we will examine the specific model of flow in the network, here the transportation problem.

Minumum cost flow problem

In the problem of minimum cost flow, we are looking for homogeneous product distribution from the factory (origin) to the sales market (destination). Suppose the number of products manufactored in each factory and the number of required products are known. Also, it is not necessary to send the products directly to the destinations, but it is possible to send it to the distribution centers through an intermediate point. In addition, transportation lines are limited in terms of line capacity. The goal in this issue is to minimize the cost of transporting products.

Consider a numerical example of the minimum cost flow problem in the figure below. Nodes are represented by numbered circles and arcs by arrows. Arcs are directional. For example, materials can be sent from node 1 to node 2, but this is not possible from node 2 to node 1. We denote the arc from node i to node j as i-j.

In the above figure, each arc is given a capacity and cost per unit of transportation, which is given next to each arc. For example, in arc (2-4), the flow can be from 0 to 4 units, and the cost of each unit passing through this arc is $2. The symbol ∞ means unlimited capacity. Finally, the numbers in parentheses next to the nodes show the amount of supply and demand. In this figure, node 1 is the origin and the amount of supply is equal to 20 units, and nodes 4 and 5 are the destinations that need 5 and 15 units, and it is the demand that is indicated by the sign -.

In the minimum cost flow problem, the goal is to find the flow pattern with minimum cost. To transform the problem into linear programming, suppose:

x_ij: is the number of units transported from node i to node j using arc i-j.

The linear programming model of minimum cost flow is presented as follows.

Equations 1 to 5 are the flow balance equations in the network. For example, the balance flow equation at node 1 is as follows.

The above equation states that the output flow from node 1 (x₁₂+x₁₃) should be equal to the supply of node 1 (20).

The balance equation in node 2 states that the input flow to node 2 (x₁₂ ) is equal to the output flow from node 2 (x₂₃+x₂₄+x₂₅ ).

The minimum cost flow model in the network has a special structure that is used to provide the solution order. Flow variables x_ij in balance equations only get 0, +1 and -1 coefficients. In addition, they appear exactly in two balance equations: once with a coefficient of +1 corresponding to the node from which they originate and -1 corresponding to the node to which they enter. According to the above, the general form of the Minumum Cost Flow is expressed as follows.

The above model is the general model of minimum cost flow. The above model can be converted into simpler forms, which we will describe below.

Shortest path problem

One of the practical applications of network theory in the real world is related to determining the shortest path in the network. In this topic, networks whose nodes are the area and region and arcs are the communication paths between these nodes. Any node of this network can be considered as the origin or the destination. The goal is to determine a path between the origin and the destination and it leads to the shortest distance, which is called the shortest path, in the network.

The networks mentioned in this course are divided into two types:

• Loopless networks

• Loop networks

In the following, we will examine each of these two types of networks.

Loopless networks

These networks are often similar to simple vector networks, but here both nodes can be considered as the origin and destination nodes of movement.

Simple shortest path method

In this method, a computational movement is performed from the origin node (start) to the destination node (end). During this computational move, each node is assigned a code (m) that represents the shortest distance of that node from the starting node. It is assumed that the number of the starting node is equal to 1 and the number of the end node is to n, and the middle nodes are also numbered in ascending order. The algorithm steps of this method are as follows:

Step 1: Assign a code equal to zero to the starting node (m₁=0).

Step 2: Get the code of node j (m_j) from the following equation:

where S is the set of nodes ending in node j and d_ij is the direct distance from node i to node j

Step 3: When the end node gets the code ( ), this code represents the shortest distance between the start node and the end node of the network.

Step 4: In order to find the shortest path, the backtracking method is used. In other words, each of the input arcs to a node, which determines the code of that node, is located on the shortest path.

Example:

Using the provided method, determine the shortest path between nodes 1 and 8 in the network shown below. The distance between both nodes is marked on the arc.

Solution:

First, the code of node 1 is considered equal to zero (m₁=0).

For node 2, we can write (m₂=m₁+d₁₂=0+4=4)

For node 3, since there are two paths to reach this node, these two paths should be considered:

Calculations for other nodes are done in the same way, the results of which are summarized in the figure below. It can be seen that the shortest distance of node 8 from node 1 is equal to 12.

Backtracking is used to determine the shortest path between nodes 1 and 8. In this movement, any node (j) whose code (m_j) applies in the relation m_i=m_j-d_ijis located on the shortest path. The movement starts from the end node, three branches are entered into this node:

Arcs (5,8) and (6,8) are on the shortest path. Therefore, there are two shortest paths so far. First, we continue working from node 5.

The arc (2,5) lies on the shortest path.

The arc (1,2) is on the shortest path. The first route was determined. Now it’s time for the second path. we continue the process from the sixth node.

The arc (4,6) is on the shortest path.

Arc (3,4) lies on the shortest path.

The arc (1,3) lies on the shortest path. It can be seen that there are two paths in this network, which has the shortest path.

The k-th shortest path

The bus driver has chosen the shortest route to take the passengers from the origin city (X) to the destination city (Z), during which he passes through the cities U, V and W. Suppose that on a particular week, there is an obstacle to go to city U, so the bus driver intends to use the second shortest route. This example shows that sometimes it is necessary to determine the second, third, or in general k-th shortest path. To determine the k-th shortest path, a change is made as follows in the second step of the simple shortest path method.

where Mink means choosing the k-th minimum value inside {}.

Example:

Determine the 1st, 2nd, 3rd shortest path between nodes 1 and 8 in the following network.

Solution:

Using the simple shortest path method, the shortest path (the first shortest path) to each node is obtained:

Regarding the second short path, the source node is still assigned a code equal to zero.

Only one branch enters node 2, so there is no second shortest distance between nodes 1 and 2:

But for node 3, we can write:

For other nodes, we proceed as follows:

The third shortest distance from the origin node to itself is also equal to zero:

Because only one branch enters node 2, there is also no third shortest distance between nodes 1 and 2.

For node 3 we have:

In the same way, we can write:

The second and third shortest paths between nodes 1 to 8 are determined using backtracking. There are two answers for the second short path and one answer for the third short path:

The second short path:

The third short route:

Three types of routes are shown in the following figures:

The shortest routes

The second short paths

The third short paths

Loop networks

In these networks there are loops, which means that between a number of nodes there is an arc to go and another arc to return. Here, two methods are described for solving problems in loop networks (finding the shortest path):

Dijkestra’s method

The Dijkestra method is named after its inventor, and two codes are assigned to each node:

m_i: the shortest distance of node i from the origin node to the current step of the algorithm, which is called the temporary code. The shortest distance may also be obtained in the next steps.

M_i: the shortest distance of node i from the origin node, which is called the permanent code, and a shorter distance will not be obtained in the next steps.

Dijkestra’s algorithm is as follows:

Step 1: Assign a permanent code equal to zero to the start node (M1=0)

Step 2: Assign a temporary code to the nodes adjacent to the nodes that have received a permanent code using the following relationship:

where d_ij is the direct distance from node i with permanent code to node j which is the temporary code:

If a node has previously received a temporary code, that code is compared with the new temporary code and a smaller code is selected. Then, among all the nodes that have received a temporary code so far, the node that has the smallest code, convert that code to a permanent code. Now, assign a temporary code to the nodes adjacent to the node that received the permanent code, and so on.

Step 3: Stop when the end (destination) node has received the permanent code. M_n represents the shortest distance between the end node and the start node.

Step 4: In order to find the shortest path, use the backtracking method with the following relation:

To clarify the steps of the algorithm, check the following example.

Example:

Determine the shortest distance and path between nodes 1 and 7 in the following network using Dijkestra ‘s method.

Solution:

The permanent code of node 1 (origin of movement) is considered equal to zero.

Because node 1 has received a permanent code, the adjacent nodes are assigned a temporary code:

The minimum number of temporary codes available so far is equal to 3, so the temporary code of node 2 becomes a permanent code:

Temporary code is given to the nodes adjacent to node 2 that received the permanent code:

Node 4 already had a temporary code equal to 5, but at this stage a new temporary code equal to 4 has been obtained for it. Since the new temporary code is smaller than the previous code, it replaces:

The minimum temporary codes available so far are 4 for node 4:

The process continues like this:

The following figure summarizes the results of different steps of the algorithm.

In order to determine the shortest path between nodes 1 and 7, backtracking is used. We continue as described in networks without loops.

The arc (6,7) is located on the shortest path.

Arcs (4,6) and (3,6) are the shortest paths.

The arc (3,4) is on the shortest path.

The arc (2,4) is on the shortest path.

The arc (1,2) lies on the shortest path.

Therefore, in this network, there are two paths that have the shortest distance:

The figure below shows the shortest network paths as follows:

Comprehensive shortest path method

Dijkestra’s algorithm is an easy method to determine the shortest path in the network, but the weakness of the method is that with each iteration of the algorithm, only the shortest distance between the two nodes of origin and destination is determined. But by implementing the comprehensive shortest path method, the shortest path between all nodes can be calculated from each other.

If the desired network has n nodes, the starting node is numbered 1 and the end node is numbered n, and other nodes are also numbered in ascending order from the starting node to the end.

In this method, two matrices of distance (D) and path (P) are defined. d_ij represents the distance of node i from node j and p_ij is the path from node i to node j. Whenever there is no direct path to reach from one node to another, the distance between them is considered ∞ , and the path between them will be marked with a “-” sign. It should be noted that the distance from one node to another node, i.e. d_ij, may not be the same as the return distance, i.e. d_ji.

For example, d₁₂ is the distance from node 1 to 2.

For example, p₁₂ is the path from node 1 to node 2.

In each stage j (j=1,2,…,n), node j is considered as an intermediary node and the route between any two nodes other than node j is obtained using this intermediary. If this distance is less than the previous distance, it will be replaced, otherwise the previous distance will be kept. In other words, the j-1 step matrices, namely D_j-1and P_j-1, will be converted into j step matrices, namely D_j and P_j, by the following relations.

More explanations are provided in the form of an example:

Example:

By applying the comprehensive shortest path method, get the shortest path between all the nodes of the network in the following figure.

Solution:

First, we form the matrices D₀ and P₀.

It starts from an arbitrary node (here node 1) and this node is considered as an intermediary. The pairwise distance of nodes 2 to 5 is evaluated through node 1:

Stage 1 (intermediary node 1): the distance between nodes 2 and 3 in the matrix is equal to ∞ , while through the intermediary node, i.e. node 1, this distance will be equal to 9. Because the distance through the intermediary is less than the distance in the matrix, it is replaced by:

Up to this stage, to get from node 2 to node 3, you have to move through node 1, and the distance is equal to 9. The same is done for other nodes:

It can be seen that at this stage the distance and route change from node 2 to 4 and also from node 3 to 2. Therefore, the matrices of this step are:

Stage 2 (intermediary node 2)

In this step, the distance and route change from node 1 to 5, from node 4 to 1, from node 4 to 3, from node 5 to 1, and from node 5 to 4. Therefore, the matrices of step 2 can be written as follows:

Stage 3 (intermediary node 3)

In step 3, only the distance and path change from node 5 to 4, and as a result, the matrices of step 3 can be obtained as follows:

Stage 4 (intermediary node 4)

In step 4, only the distance and path change from node 3 to 2, and as a result, the matrices of step 4 can be obtained as follows:

Stage 5 (intermediary node 5)

At this stage, the distance and route changes from node 2 to 3 and also from node 4 to 3. Therefore, the matrices of this step (final matrix) are:

The algorithm ends and the shortest distance between the two nodes can be obtained from the D₅ matrix. The corresponding path can also be traced through the P₅ matrix. As an example, the shortest distance between node 2 and node 4 in matrix D₅ is equal to 9 distance units. From matrix P₅, the shortest path from node 2 to node 4 is through node 1. The shortest path from node 1 to node 4 is through node 4.

Example:

Find the shortest path and distance from node 1 to node 12 in the network shown below.