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

Constraints

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

PuLP

Tutoral: https://coin-or.github.io/pulp/

Results: Find the shortest path between two points on a graph

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