shortest_path_by_LP

Solve the shortest path problem using PuLP, a python library used to model linear programming problems

Consider a shortest path problem as a linear programming problem

In order to solve a shortest path problem by using PuLP, the problem should be transformed into a linear programming problem.

First, identify the objective function, costs and constraints

◆ Objective function: the shortest distance
◆ Costs: adjacency matrix

Any complete path must follow the constraints:

For instance, a complete path A->B->E->F

can be represented as a matrix shown below

Figure below explains how the path follows the constraints

A graph with 250 randomly-generated points

Successfully find the shortest path between p1 to p2

Successfully find the shortest path between p89 to p250