Introduction

The all pairs shortest path problem is one of the most important issues in the field of operations research. In this problem, we are looking for the shortest path in a weighted graph for all pairs origin-destinaiton (O-D). In Lesson 7 of Optimization City website, the shortest path algorithm is teaching with numerous examples.

Instructions of using online solver of the all pairs shortest path problem

The GUI of the online solver of the all pairs shortest path problem is as follows:

Input data

To solve the all pairs shortest path, the required inputs are:

n: the number of nodes of the graph.

big: a large enough number that is at least equal to the sum of the weights of the edges of the graph.

startnode: the origin node

endnode: destination node

dist: matrix has n+1 rows and n+1 columns. The first row and the first column of this matrix are equal to zero. If there is no edge in the network, the value of that edge in this matrix is equal to the number big.

Example

For the following network, find the shortest path for all source-destination pairs. Edges that are undirected can be replaced by two directed arcs with two different directions.

 

Solution:

The input data for a given network is as follows.

Entering information in the online solver of the shortest path for all pairs is as follows.

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

The result of running the algorithm is as follows.

In the output part, the shortest path matrix for all source-destination pairs is given. For example, consider the first line. The first component is equal to zero. That is, the shortest path from node 1 to 1 is equal to zero, which is logical. The second component is the length of the shortest path from node 1 to node 2, which is equal to 8. And in the same way for other components of this matrix, the shortest path of source-destination pairs is determined.