**Introduction**

The** k shortest paths problem** is one of the most important problems in the field of operations research. In this problem, we seek to find the k shortest paths in a weighted network between the origin and the destination, where k is an integer. For example, consider the following network. For more information, you can refer to lesson 7 of **Optimization City** group.

**Instructions of using online solver of the k shortest paths problem **

The GUI of the online solver of the k shortest paths problem is as follows.

**Input data**

To find the k shortest paths, the required inputs are as follows:

**n:** the number of input network nodes

**m:** the number of arcs of the input network

**source:** source node

**sink:** destination node

**k:** the number of the shortest path from the source node to the sink node

**pathnodes:** A vector has two components. The first component or pathnodes[0] determines the maximum number of nodes in the shortest path despite repetition in nodes, which is an integer. The second component or pathnodes[1] determines the maximum number of the shortest path from the source to the sink destination.

**nodei:** a vector that specifies the initial node of the arcs and its size is for m+1.

**nodej:** a vector that specifies the end node of the arcs and its size is for m+1.

**weight:** A vector that specifies the weight or cost of bows and its size is equal to m+1.

**Note 1:** This solver has the possibility of using negative weights for arcs.

**Note 2:** The weights of the arcs must be **Integer**.

**Note 3:** The first component of the vectors nodei, nodej, and weight should be considered as zero.

**Example**

We use the following example to teach how to use this solver. We are looking to find the 3 shortest paths in the following network from node 5 to all nodes that are allowed to repeat nodes in the path (the maximum number of nodes allowed in this case is equal to 20). Also, we determine at most 6 shortest paths from node 5 to node 4.

**Solution**

The input information for the given network is as follows.

Entering information in the online solver for the k shortest paths is as follows.

After entering the data, we click on the **RUN** button.

The result of running the algorithm is as follows.

In the first part of the output, the 3 shortest paths from the origin node or 5 to all nodes are given. For example, the first shortest path from node 5 to node 1 equals 4; the second shortest route 9; And the third shortest path is equal to 10.

In the second part, the 6 shortest routes from node 5 to node 4 are given. In case of problem, it has been said that maximum 6 shortest routes should be stated. In some cases, when the number of all routes is less than this number, it reports the number of six routes.