Shortest Path Problem Analysis: Data Science Report - University

This report examines the shortest path problem, focusing on its application in data science and related fields. It begins by outlining the problem itself, which involves finding the shortest route between a source and destination within a network, often represented by nodes and arcs with associated distances. The report then delves into the application of linear programming as a method for solving this problem, providing the relevant mathematical formulation. Additionally, it discusses Dijkstra's algorithm, another technique used to find the shortest paths, highlighting its two types of node labels (temporary and permanent) and its applicability in statistical programming environments like R-programming and R-studio. The report also touches upon real-world applications, such as transportation networks, and the use of cyclic, undirected, and directed graphs as visualization tools. The report concludes by emphasizing the relevance of these techniques in various scenarios, including inventory planning and project scheduling.

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.