CHAPTER 3

SHORTEST ROUTE PROBLEM

3.1 INTRODUCTION
The Shortest Route Problem (SRP) is a network model problem that focuses on
finding the path between two nodes in a network that minimizes total cost, distance, or time.
In a network, nodes represent locations or events, and arcs represent possible paths with
associated weights (such as distance or travel time). This problem is essential in various
fields because it enables efficient movement or transfer from a source to a destination,
whether in transportation, logistics, or mapping, to ensure efficient movement from one
location to another.
Food delivery platforms like Swiggy and Uber Eats use the short-route method in
their route optimization systems to ensure timely and efficient deliveries. However, their
systems go beyond choosing the shortest distance—they also factor in real-time data such as
traffic, weather, and driver availability. When a customer places an order, the delivery
system: 1. Locates the nearest available delivery executive.
2. Calculates multiple possible routes from the restaurant to the customer.
3. Assigns the order to the driver who can reach the customer fastest, not just by
distance but by expected travel time.

3.2 HISTORY OF THE SHORTEST ROUTE PROBLEM

The Shortest route (or shortest path) problem has a rich and fascinating history
that spans centuries. Here’s a detailed overview:
Early Foundations (18th-19th centuries)
1. Leonhard Euler (1707-1783): Euler’s work on the seven bridges of Konigsberg
problem (1736) laid the foundation for graph theory, which is crucial for shortest
route problems. Euler’s solution introduced the concept of Eulerian paths and circuits.
2. William Rowan Hamilton (1805-1865): Hamilton worked on the Icosian Game, a
mathematical puzzle that involves finding a Hamiltonian cycle in a graph. This work
predates modern graph theory and the shortest path algorithms.
Development of Algorithms (20th century)
1. Edward F. Moore (1925-2003): Moore developed an algorithm for finding shortest
paths in graphs in the 1950s. Although not as widely used as Dijkstra’s algorithm,
Moore’s work contributed to the development of shortest route algorithms.
2. Edsger W. Dijkstra (1930-2002): Dijkstra introduced his famous algorithm for
finding the shortest route in graphs in 1959. Dijkstra’s algorithm is still widely used
today due to its efficiency and simplicity. His algorithm quickly became a cornerstone
of graph theory and operations research, widely used in transportation, networking,
and logistics.

17
3.3 APPLICATION OF SHORTEST ROUTE PROBLEM
1. Transportation and Navigation
● Route Planning for Vehicles: Shortest path algorithms are fundamental in GPS
navigation systems (like Google Maps, Waze) to provide drivers with the quickest or shortest
route between two locations, factoring in real-time traffic, road closures, and distances.

● Emergency Response: Fire departments and ambulance services use these algorithms to
ensure the fastest possible route to emergencies, minimizing response times and potentially
saving lives.

● Logistics and Delivery: Companies optimize delivery routes from warehouses to

customers, reducing travel time, fuel costs, and improving overall efficiency.

2. Telecommunications and Computer Networks

● Data packet routing: In computer and telecommunication networks, shortest path
algorithms help determine the most efficient path for data packets, reducing transmission
delays and optimizing bandwidth usage.

● IoT Networks: In Internet of Things (IoT) environments, shortest path routing

algorithms are used to optimize communication between devices, considering factors like
latency and energy consumption. Algorithms like Dijkstra’s and Bellman-Ford are adapted
for dynamic and complex IoT networks.

3. Facility layout and Robotics

● Factory and plant Optimization: Shortest path algorithms help design efficient layouts
in factories and guide robots or Automated Guided Vehicles (AGVs) along optimal paths to
minimize operational time and costs.

● Fault Detection: In production plants, these algorithms can be used to quickly identify
the most efficient inspection or repair routes for maintenance teams.

4. Social Networks and Recommendation Systems

● Connection Analysis: Algorithms are used to measure the minimum number of
connections between users, enabling features like friend recommendations and analyzing
network influence (e.g., six degrees of separation).

● Information Spread: Helps model and optimize the spread of information or viral
content within a network.

5. Urban Planning and Public Services

● Public Transport Design is used to design efficient routes for buses, trains, and waste
collection vehicles, minimizing travel distance and time. Algorithms suggest that tourists
should visit multiple attractions, as demonstrated in studies of city navigation.

18
3.4 DEFINITIONS

3.3.1 Shortest route problem:

The Shortest route problem (also known as the shortest path problem) is the task of
finding a path between two nodes (N) in a network such that the sum of the weights of its
constituent arcs (A) is minimized, which means finding the most efficient route from a
starting point to a destination, where efficiency is measured by distance, time, or cost.

3.3.2 Network:

A network is a graphical representation of a system or project, consisting of a set of

points called nodes, connected by lines called arcs. Each node represents an activity, event,
location, or state, while each arc represents a relationship, route, or flow between nodes.

Types of Network:

1. Directed network: A directed network (or digraph) is a network where the arcs
between nodes have a specific direction, usually represented by arrows. Each arc
goes from one node to another, indicating a one-way relationship or flow.
For example, in the above diagram, there is a directed arc from A to B, B to C, C to
D, and D to A.
B

A C

2. Undirected Network: An undirected network is a network where the arcs between

nodes are bidirectional and have no inherent direction. If node A is connected to
node B, then B is also connected to A.
B

3. Mixed Network: A mixed network is a network that contains both directed and
undirected arcs. Some arcs have a specific direction, while others are bidirectional.
Mixed networks are used to model systems where both one-way and two-way
relationships exist.

19
3.5 SHORTEST ROUTE ALGORITHMS
There are standard algorithms for solving the shortest route problems. Two of them
will be considered now. They are
1. Dijkstra’s Algorithm
2. Floyd’s Algorithm

3.5.1 Dijkstra’s Shortest Route Algorithms

Dijkstra’s algorithm seems to be the most efficient one among several algorithms
proposed for the shortest route between a special node pair.
Let the problem be to find the shortest path from node 1 to node i in a connected
weighted graph.
Let 𝑢𝑖 be the shortest distance from source node 1 to node i, and define 𝑑𝑖𝑗 (≥, 0) as
the length of arc (i, j).
The algorithm defines the label for an immediately succeeding node j as 𝑢𝑗 ,
[𝑢𝑗 , i] = [𝑢𝑖 + 𝑑𝑖𝑗 ], 𝑑𝑖𝑗 ≥ 0.

We take the label for the starting node as [0, -1], indicating that the node has no
predecessor. There are two types of node labels in Dijkstra’s Algorithm: (i) temporary node
and (ii) Permanent node.
A temporary label at a node is modified if a shortest route to the node can be found.
Otherwise, the temporary status is made permanent.
Step 0: Label the source node (i.e., node 1) with permanent labels [0,-1], set i = 1.
Step i: a) Compute the temporary labels [𝑢𝑖 + 𝑑𝑖𝑗 , i] for each node j with 𝑑𝑖𝑗 > 0 provided j
is not permanently labelled. If node j already has an existing temporary label [𝑢𝑗 , k] through
another node k, and if 𝑢𝑖 + 𝑑𝑖𝑗 < 𝑢𝑗 replace [𝑢𝑗 , k] with [𝑢𝑖 + 𝑑𝑖𝑗 , i].

b) If all the nodes have permanent labels, stop. Otherwise, select the label [𝑢𝑟 , s]
having the shortest distance (= 𝑢𝑟 ) among all temporary labels ( break ties arbitrarily), set i =
r and repeat step i.

Example:
1) Find the Shortest path from node 1 to node 5 of the distance network shown in the
above figure using Dijkstra’s algorithm.

20
 2

1 20 4

3 60 5

Solution: 100
∞
2
40

0 1 20 4 ∞

3 60 5 ∞
∞
30 90

Dijkstra’s Algorithm d(i) + C(i, j) ≤ d(j)

Selected Visited d(2) d(3) d(4) d(5)

Vertex Arc

1 {1} 100 30 ∞ ∞

2 {1,3} 100 30 40 ∞

3 {1,3,4} 55 30 40 90

5 {1,3,4,2,5} 55 30 40 90

The shortest distance of the given network, node 1 – 2 = 55, node 1 – 3 = 30 [1-3-4-2],
node 1 – 4 = 40 [1-3-4], and node 1 – 5 = 90 [1-3-5 or 1-3-4-5].

3.5.1.1 Dijkstra’s Shortest Route Algorithm in FDS

Focusing on the order feature, we formulate a solution focusing on the allocation of
delivery men using Dijkstra’s algorithm. This is used to find the shortest path between the

21
start and the endpoint. It picks unvisited nodes with the lowest distance, calculates the
distances through it to each unvisited neighbor, and updates the neighbor’s distance if
smaller. This solution suggests how many delivery men should be allocated depending on the
number of restaurants and their distance.
The time taken for delivery will depend on:

● Distance of the delivery men from the restaurant.

● Distance between the restaurants.

● Distance between the last restaurant and the customer’s location.

Note:
1. In FDS, nodes represent Restaurants, customers' zones or areas, and intersection points.
2. Arcs represent distance or time from one node to another.
Example:
1. A delivery driver starts at Restaurant R1, must pick up an additional order at Restaurant
R2, and then delivers to Customers C1, C2, and C3. The travel distance between each
location is as follows. Find the shortest route from R1 (pickup at restaurant R1) to R2
(pickup at restaurant R2) for customers C1, C2, and C3(Customer).
12
R1 C1

5
8 C2

3
R2 C3
14

Solution:

11
12 ∞
0 R1 C1

5
8 C2 ∞
15
3
R2 C3
∞ 14 ∞
5 18

22
Dijkstra’s Algorithm d(i) + C(i, j) ≤ d(j)

Selected
Vertex Visited Arc d(R2) d(C1) d(C2) d(C3)

R1 {R1} 5 12 16 19

R2 {R1, R2} 5 11 19 19

C1 {R1, R2, C1} 5 11 15 19

C3 {R1, R2, C1, C3,} 5 11 15 18

C2 {R1, R2, C1, C3, 5 11 15 18

C2}
The shortest route from Restaurant R1 to R2 (pickup) to deliver to all customers (C1, C2,
C3)
R1 – C3 = {R1, R2} + {R2, C1} + {C1, C2} + {C2, C3}
=5+6+4+3
R1 - C3 = 18 [R1 – R2 – C1 – C2 – C3]

3.5.1.2 Exercise
1. A delivery driver starts at Restaurant R1, must pick up an additional order at Restaurant
R2, and then deliver to Customers C1, C2, and C3. The travel times (in minutes) between
each location are as follows:
C1

6
4 C2
R1 R2 10

C3

What is the optimal sequence of stops for the delivery agent to minimize total delivery time?
Ans: [R1 – R2 – C1 – C2 – C3 = 4 + 6 + 3 + 2 = 15 min]

23
 2. Uber Eats has to deliver food to the customer within 20 minutes, where node A is the
restaurant, node E is the customer's house, and the remaining nodes are different areas that
the deliveryman has to cross. Find the shortest route to deliver a portion of food within 20
minutes.

A C

B D

[ Here, A – B = 4km, A – C = 2km, C – B = 1km, B – D = 5km, C – D = 8km, C – E = 10km,

D – E = 2km, B – E = 7km].
Ans: [ A – C – B – D – E = 2 + 1 + 5 + 2 = 10km]

24
3.5.2 Floyd’s Shortest Route Algorithm
Floyd’s Algorithm finds the shortest path and the corresponding distance from any
source node to any destination node in a given distance network.
This algorithm takes the initial distance matrix and initial precedence matrix [𝑃0 ] as
input, then it performs n iterations (n is the number of nodes in the distance or time matrix)
and generates the final distance matrix [𝐷𝑛 ] and the final precedence matrix [𝑃𝑛 ]. One can
find the shortest distance between any two nodes from the final distance matrix [𝐷𝑛 ] and can
trace the corresponding path from the final precedence matrix [𝑃𝑛 ].
Step 1: Set k = 0.
Step 2: From the initial distance matrix [𝐷0 ] and the initial precedence matrix [𝑃0 ] from the
distance network.
The distance matrix and the precedence matrix have n rows and n columns. In the
distance matrix, between any two nodes, if there is no direct arc, the corresponding distance
is assumed as ∞. The diagonal values of the initial distance matrix are assumed as 0. In the
initial precedence matrix, the diagonal values are assumed as ̔ –̕ , and the other entries in the
𝑖 𝑡ℎ row are assumed as I, for I = 1, 2, 3, ........, n.
Step 3: Set k = k + 1.
Step 4: Obtain the values of the distance matrix [𝐷𝑘 ] for all the cells where I is not equal to j
using the following formula.
𝐷𝑖𝑗𝑘 = min[𝐷𝑖𝑗𝑘 , (𝐷𝑖𝑘
𝑘−1 𝑘−1
+ 𝐷𝑘𝑗 )]

Step 5: Obtain the values of the precedence matrix, [𝑃𝑘 ] for all the cells where I is not equal
to j.
Using the following formula,

𝑃𝑖𝑗𝑘 = 𝑃𝑘𝑗
𝑘+1
, if 𝐷𝑖𝑗𝑘 is not equal to 𝐷𝑖𝑗𝑘−1

= 𝑃𝑖𝑗𝑘−1, Otherwise.

Step 6: If b = n, go to step 7. Otherwise, set k = k + 1 and go to step 4.

Step 7: For each source-destination node combination, as required in reality, find the shortest
distance from the final distance matrix [𝐷𝑛 ] and trace the corresponding shortest path from
the final precedence matrix [𝑃𝑛 ]. Guidelines for tracing the shortest path for a given
combination of source node and destination node are presented below.
(i) Let the source node be X and the destination node be Y.
(ii) Fix node Y as the last node in the partially formed shortest path.
(iii) Find the value from the final precedence matrix [𝑃𝑛 ] for the row corresponding to
node X and the column corresponding to Y. Let it be Q prefix node Q in the partially formed
shortest path.

25
 (iv) Check whether Q is equal to X. If not so, set y = Q and go to step (iii); Otherwise,
go to step (v).
(v) The path constructed is the required shortest path from the source node X to the
destination node Y.
Example
3. Suppose there is a network with nodes A, B, and C. Using Floyd’s Algorithm, find the
shortest distance between all pairs of nodes.
2
A B
a
3

C D
1
Iteration 0:
𝑨 𝑩 𝑪 𝑫
𝑨 0 ∞ 3 ∞
𝑩 2 0 ∞ ∞
𝑫𝟎 = [ ]
𝑪 ∞ 7 0 1
𝑫 6 ∞ ∞ 0
Iteration 1:
𝑨 𝑩 𝑪 𝑫
𝑨 0 ∞ 3 ∞
𝑩 2 0 5 ∞
𝑫𝟏 = [ ]
𝑪 ∞ 7 0 1
𝑫 6 ∞ 9 0
Iteration 2:
𝑨 𝑩 𝑪 𝑫
𝑨 0 ∞ 3 ∞
𝑩 2 0 5 ∞
𝑫𝟐 = [ ]
𝑪 9 7 0 1
𝑫 6 ∞ 9 0
Iteration 3:
𝑨 𝑩 𝑪 𝑫
𝑨 0 10 3 4
𝑩 2 0 5 6
𝑫𝟑 = [ ]
𝑪 9 7 0 1
𝑫 6 16 9 0

26
Iteration 4:
𝑨 𝑩 𝑪 𝑫
0𝑨 10 3 4
𝟒 2𝑩 0 5 6
𝑫 = [ ]
𝑪 7 7 0 1
𝑫 6 16 9 0
The shortest path from node A to D is A – C – D
Length is 4 units.

3.5.3 Floyd’s Shortest Route Algorithm in FDS

In Food Delivery Systems, unlike Dijkstra’s Algorithm, which finds the shortest
path from a single source, Floyd’s Algorithm computes the shortest paths between all pairs of
locations at once. This is ideal for food delivery systems that need to quickly answer distance
queries between any restaurant, customer, or delivery hub. When restaurants, customers, and
hubs are interconnected, Floyd’s Algorithm ensures the system always finds the shortest
route, even if it involves multiple intermediate stops. This algorithm can be extended to not
only find the shortest distances but also reconstruct the actual delivery routes, aiding in real-
time navigation and logistics planning.

Example: Find the shortest route between every two nodes for the given network. In the
network, the customer’s house is the central node and four restaurants (R1 - R4) are around
the customer’s house. The goal is to use Floyd’s algorithm to help the customer find the
nearest restaurant.

R2 5
C

R1

R3 15 R4

Iteration 0:
𝑪 𝑹𝟏 𝑹𝟐 𝑹𝟑 𝑹𝟒

𝑪 0 ∞ 5 6 4
𝑹𝟏 ∞ 0 3 10 ∞
𝑫𝟎 = 𝑹𝟐 5 3 0 ∞ ∞
𝑹𝟑 6 10 ∞ 0 15
𝑹𝟒 [ 4 ∞ ∞ 15 0]

27
Iteration 1:
𝑪 𝑹𝟏 𝑹𝟐 𝑹𝟑 𝑹𝟒

𝑪 0 ∞ 5 6 4
𝑹𝟏 ∞ 0 3 10 ∞
𝑫𝟏 = 𝑹𝟐 5 3 0 11 9
𝑹𝟑 6 10 11 0 10
𝑹𝟒 [ 4 ∞ 9 10 0]
Iteration 2:
𝑪 𝑹𝟏 𝑹𝟐 𝑹𝟑 𝑹𝟒

𝑪 0 ∞ 5 6 4
𝑹𝟏 ∞ 0 3 10 ∞
𝑫𝟐 = 𝑹𝟐 5 3 0 11 9
𝑹𝟑 6 10 11 0 10
𝑹𝟒 [ 4 ∞ 9 10 0]
Iteration 3:
𝑪 𝑹𝟏 𝑹𝟐 𝑹𝟑 𝑹𝟒

𝑪 0 8 5 6 4
𝑹𝟏 8 0 3 10 12
𝟑
𝑫 = 𝑹𝟐 5 3 0 11 9
𝑹𝟑 6 10 11 0 10
𝑹𝟒 [4 12 9 10 0]
Iteration 4:
𝑪 𝑹𝟏 𝑹𝟐 𝑹𝟑 𝑹𝟒

𝑪 0 8 5 6 4
𝑹𝟏 8 0 3 10 12
𝟒
𝑫 = 𝑹𝟐 5 3 0 11 9
𝑹𝟑 6 10 11 0 10
𝑹𝟒 [4 12 9 10 0]
Iteration 5:
𝑪 𝑹𝟏 𝑹𝟐 𝑹𝟑 𝑹𝟒

𝑪 0 8 5 6 4
𝑹𝟏 8 0 3 10 12
𝑫𝟓 = 𝑹𝟐 5 3 0 11 9
𝑹𝟑 6 10 11 0 10
𝑹𝟒 [4 12 9 10 0]
The above iteration shows the shortest route between every restaurant and customer. The
restaurant, which is near the customer's house is R4, and the second nearest restaurant is R2.

28