Surname: 1 Student’s Name: Professor’s Name Course Name: Date:

Surname: 1
Student’s Name:
Professor’s Name
Course Name:
Date:
Shortest Path Problems in Linear Programming (LP)
The topic of shortest path seeks to aid in the determination of the shortest routes from a starting node to
a destination node or all nodes in the network. Shortest path assessment technique is normally employed in the
solving of transportation problems. In the real world, this technique is employed by researchers in an attempt to
find the shortest way from point A to point B. Other examples of real world problems that utilized shortest path
technique are inventory planning, equipment replacement, project scheduling, and capital investment. The most
utilized visualization and assessment tools are cyclic, undirected, and directed graphs. There are essentially five
problems that fall under the graphical approach of shortest path assessment and they are: single-pair shortest
path problem, single-source shortest path problem, single-destination shortest path problem, all-pairs shortest
path problem, and shortest cycle through a given node. The formula for the shortest path problem is presented
as follows:
Minimize Z=∑
i
∑
j
cij xij
Subject to:
∑
j
xij−∑
k
xki = {
1 , if i=s ( source ) ;
0 ,otherwise ;
−1 ,if i=t ( sink ) ;
0 ≤ xij for all arcs i= j∈the network
A side from the linear programming technique to finding the shortest path another useful technique is
Dijkstra’s Algorithm. There are two types of node labels under Dijkstra’s algorithm these are temporary and

Surname: 2
permanent. The process start with the denotation o the source node with a permanent label [0,-]. The other
nodes are assigned temporary labels sequentially and the process is stopped when all nodes have permanent
labels. This algorithm can be easily employed in statistical programs like R-programming and R-studio for
quick computations.