Special Transport Algorithms for

Road Network Analysis

Shortest path analysis

Minimum spanning tree
 Minimal Spanning Tree Problem
Example: The Municipal planner would like to make sure that all barangays of his
town are connected with good roads, since some barangays have multiple road
connections and because of limited budget for maintenance, determine the least
possible way (in km) of connecting all these barangays. The values connecting the
towns are in kilometers.

Barangays
2

5 4 4
10 5 7
1 3 5
1 3 9
2 9
7 8 8
4 6
3

Simple Method: Connect adjacent nodes with the least distance, no cycle
allowed
Let G denote the links in the minimal spanning tree

1st Iteration: G = {(1,3)}

Minimum distance = 1 km

5 4 4
10 5 7
1 3 5
1 3 9
2 9
7 8 8
4 6
3
2nd Iteration: G = {(1,3), (3,4)}
Minimum distance = (1 + 2) = 3 km

5 4 4
10 5 7
1 3 5
1 3 9
2 9
7 8 8
4 6
3
3rd Iteration: G = {(1,3), (3,4), (4,6)}
Minimum distance = (1 + 2 + 3) = 6 km

5 4 4
10 5 7
1 3 5
1 3 9
2 9
7 8 8
4 6
3
4th Iteration: G = {(1,3), (3,4), (4,6), (5,6)}
Minimum distance = (1 + 2 + 3 + 3) = 9 km

5 4 4
10 5 7
1 3 5
1 3 9
2 9
7 8 8
4 6
3
5th Iteration: G = {(1,3), (3,4), (4,6), (5,6), (2,3)}
Minimum distance = (1 + 2 + 3 + 3 + 4) = 13 km

5 4 4
10 5 7
1 3 5
1 3 9
2 9
7 8 8
4 6
3
6th Iteration: G = {(1,3), (3,4), (4,6), (5,6), (2,3), (5,7)}
Minimum distance = (1 + 2 + 3 + 3 + 4 + 4) = 17 km

5 4 4
10 5 7
1 3 5
1 3 9
2 9
7 8 8
4 6
3
7th Iteration: G = {(1,3), (3,4), (4,6), (5,6), (2,3), (5,7), (7,8)}
Minimum distance = (1 + 2 + 3 + 3 + 4 + 4 + 5) = 22 km

5 4 4
10 5 7
1 3 5
1 3 9
2 9
7 8 8
4 6
3
 Minimal Spanning Tree Problem
Summary of results:
1. The final minimal spanning tree is as shown below. Its length is equal to (1 + 4 + 2 +
3 + 3 + 4 + 5 ) 22 kms
2. The difference between the minimal spanning tree problem and the shortest route
problem is that the latter is based from a source node and all the other nodes are
linked to it in the shortest possible way.
3. While the minimal spanning tree problem connects one node to another node the
minimal way without regard to any source node.

5 4 4
10 5 7
1 3 5
1 3 9
2 9
7 8 8
4 6
3
 ASSIGNMENT

Problem: For the road

network of Guimaras as
1 Jordan shown, apply the minimal
spanning tree method by
connecting all important
locations in Guimaras to the
provincial capital Jordan.
 5.9 13
2.1
12 4.9
11 2.7 10
3.7 3.3 14
9 1.6
8 6.2
4.4 3.1
6 1.2 6.0
7 15
2.5 6.0 16
5 4.6 3.8
2.8 3.3

1 Jordan 1 Jordan
3.4 12.4
2.0
3 2 17

5.1 10.2
4 8.9 10.0

3.1
31 32 18 4.0
3.0
3.8 19
2.5 30
28 8.3
29 3.4 4.4 8.2
27 2.4 3.3

3.5 26 2.0 22 3.0

2.4 23 2.9 21 20
25 1.0

4.9 5.0

24
Note: Values are in km
Link Estimated Link Estimated
Distance (km) Distance (km) MINIMAL SPANNING TREE
1-2 3.4 16-17 3.3 (Jordan as Center Node)
1-5 2.8 17-19 10.0 5.9
2.1 13
1-17 12.4 18-19 4.0 12 4.9
11 2.7 10
1-18 10.2 18-21 8.3 3.7 3.3 14
9 1.6
1-32 8.9 19-20 8.2 8 6.2
4.4 3.1
6 1.2 6.0
2-3 2.0 20-21 1.0 7
2.5 6.0 15 16
2-4 5.1 21-22 3.0 5 4.6 3.8
5-6 2.5 22-23 2.9 2.8 3.3
1 Jordan
3.4 12.4
2.0
5-7 4.6 22-28 4.4 3 2 17
6-8 4.4 23-24 5.0 5.1 10.2
7-8 1.2 23-26 2.0
4 8.9 10.0
7-9 3.1 26-28 3.3
7-15 6.0 24-25 4.9 3.1
31 32 18 4.0
3.0
8-11 3.7 25-26 2.4 3.8 19
9-10 1.6 25-27 3.5 2.5 30
28 8.3
9-11 3.3 26-27 2.4 29 3.4 4.4 8.2
10-12 2.7 26-28 3.3 27 2.4 3.3

11-12 2.1 28-32 3.8 3.5 26 2.0 22 3.0

12-13 5.9 27-30 3.4 2.4 23 2.9 21 20
25 1.0
13-14 4.9 29-30 2.5
14-15 6.2 30-31 3.0 4.9 5.0

14-16 6.0 31-32 3.1 24

Note: Values are in km
15-16 3.8
Link Estimated Link Estimated
Distance (km) Distance (km) MINIMAL SPANNING TREE
1-2 3.4 16-17 3.3 (Buenavista as Center Node)
1-5 2.8 17-19 10.0 5.9
2.1 13
1-17 12.4 18-19 4.0 12 4.9
11 2.7 10
1-18 10.2 18-21 8.3 3.7 3.3 14
9 1.6
1-32 8.9 19-20 8.2 8 6.2
4.4 3.1
6 1.2 6.0
2-3 2.0 20-21 1.0 7
2.5 6.0 15 16
2-4 5.1 21-22 3.0 5 4.6 3.8
2.8 Buenavista 3.3
5-6 2.5 22-23 2.9
3.4 12.4
2.0 1
5-7 4.6 22-28 4.4 3 2 17
6-8 4.4 23-24 5.0 5.1 10.2
7-8 1.2 23-26 2.0
4 8.9 10.0
7-9 3.1 26-28 3.3
7-15 6.0 24-25 4.9 3.1
31 32 18 4.0
3.0
8-11 3.7 25-26 2.4 3.8 19
9-10 1.6 25-27 3.5 2.5 30
28 8.3
9-11 3.3 26-27 2.4 29 3.4 4.4 8.2
10-12 2.7 26-28 3.3 27 2.4 3.3

11-12 2.1 28-32 3.8 3.5 26 2.0 22 3.0

12-13 5.9 27-30 3.4 2.4 23 2.9 21 20
25 1.0
13-14 4.9 29-30 2.5
14-15 6.2 30-31 3.0 4.9 5.0

14-16 6.0 31-32 3.1 24

Note: Values are in km
15-16 3.8
 Shortest Path Method
Example: The municipal planning engineer would like to identify the shortest path
coming from all the 7 barangays of the municipality going to the municipal center
and vice-versa. The roads along these shortest paths will be made into all-weather
roads to make them passable all year round. The values along the links are in
kilometers.

Barangays
2

5 4 4
10 5 7
Municipal
1 3 5
Center 1 3 9
2 9
7 8 8
4 6
3

Method of Analysis: Dijkstra’s Algorithm

Solution:
This is a shortest-route problem which can be solved using the Dijkstra’s Algorithm.

1st Iteration:
Nodes 1 2 3 4 5 6 7 8
L(1) 0 5 1 7    
(km)
*
2

5 4 4
10 5 7
1 3 5
1 3 9
2 9
7 8 8
4 6
3
2nd Iteration:

Nodes 1 2 3 4 5 6 7 8
L(2) 0 5 1 7    
(km)
* *
2

5 4 4
10 5 7
1 3 5
1 3 9
2 9
7 8 8
4 6
3
3rd Iteration:

Nodes 1 2 3 4 5 6 7 8
L(3) 0 5 1 3 11 10  
(km)
* * *
2

5 4 4
10 5 7
1 3 5
1 3 9
2 9
7 8 8
4 6
3
4th Iteration:

Nodes 1 2 3 4 5 6 7 8
L(2) 0 5 1 3 11 6  
(km)
* * * *
2

5 4 4
10 5 7
1 3 5
1 3 9
2 9
7 8 8
4 6
3
5th Iteration:

Nodes 1 2 3 4 5 6 7 8
L(2) 0 5 1 3 11 6  
(km)
* * * * *
2

5 4 4
10 5 7
1 3 5
1 3 9
2 9
7 8 8
4 6
3
6th Iteration:

Nodes 1 2 3 4 5 6 7 8
L(6) 0 5 1 3 9 6 15 14
(km)
* * * * * *
2

5 4 4
10 5 7
1 3 5
1 3 9
2 9
7 8 8
4 6
3
7th Iteration:

Nodes 1 2 3 4 5 6 7 8
L(6) 0 5 1 3 9 6 13 14
(km)
* * * * * * *
2

5 4 4
10 5 7
1 3 5
1 3 9
2 9
7 8 8
4 6
3
8th Iteration:

Nodes 1 2 3 4 5 6 7 8
L(6) 0 5 1 3 9 6 13 14
(km)
* * * * * * * *

5 4 4
10 5 7
1 3 5
1 3 9
2 9
7 8 8
4 6
3
Shortest Path Method
Summary of observation:
1. Road segments 1-3, 3-2, 3-4, 4-6, 6-5, 5-7, and 6-8 are roads to be
converted to all-weather roads.
2. Therefore, shortest paths from the municipality (Node 1) to each
barangays are the ff:
Brgy 1 to Brgy 2: 5 km
Brgy 1 to Brgy 3: 1 km
Brgy 1 to Brgy 4: 3 km
Brgy 1 to Brgy 5: 9 km
Brgy 1 to Brgy 6: 6 km
Brgy 1 to Brgy 7: 13 km
Brgy 1 to Brgy 8: 14 km
2

5 4 4
10 5 7
1 3 5
1 3 9
2 9
7 8 8
4 6
3
 ASSIGNMENT

Problem: For the road

network of Guimaras as
1 Jordan shown, apply the shortest
path method by connecting
all important locations in
Guimaras to the provincial
capital Jordan.
 5.9 13
2.1
12 4.9
11 2.7 10
3.7 3.3 14
9 1.6
8 6.2
4.4 3.1
6 1.2 6.0
7 15
2.5 6.0 16
5 4.6 3.8
2.8 3.3

1 Jordan 1 Jordan
3.4 12.4
2.0
3 2 17

5.1 10.2
4 8.9 10.0

3.1
31 32 18 4.0
3.0
3.8 19
2.5 30
28 8.3
29 3.4 4.4 8.2
27 2.4 3.3

3.5 26 2.0 22 3.0

2.4 23 2.9 21 20
25 1.0

4.9 5.0

24
Note: Values are in km
Link Estimated Link Estimated
Distance (km) Distance (km) SHORTEST PATH METHOD
1-2 3.4 16-17 3.3 (Jordan as Center Node)
1-5 2.8 17-19 10.0 5.9
2.1 13
1-17 12.4 18-19 4.0 12 4.9
11 2.7 10
1-18 10.2 18-21 8.3 3.7 3.3 14
9 1.6
1-32 8.9 19-20 8.2 8 6.2
4.4 3.1
6 1.2 6.0
2-3 2.0 20-21 1.0 7
2.5 6.0 15 16
2-4 5.1 21-22 3.0 5 4.6 3.8
5-6 2.5 22-23 2.9 2.8 3.3
1 Jordan
3.4 12.4
2.0
5-7 4.6 22-28 4.4 3 2 17
6-8 4.4 23-24 5.0 5.1 10.2
7-8 1.2 23-26 2.0
4 8.9 10.0
7-9 3.1 26-28 3.3
7-15 6.0 24-25 4.9 3.1
31 32 18 4.0
3.0
8-11 3.7 25-26 2.4 3.8 19
9-10 1.6 25-27 3.5 2.5 30
28 8.3
9-11 3.3 26-27 2.4 29 3.4 4.4 8.2
10-12 2.7 26-28 3.3 27 2.4 3.3

11-12 2.1 28-32 3.8 3.5 26 2.0 22 3.0

12-13 5.9 27-30 3.4 2.4 23 2.9 21 20
25 1.0
13-14 4.9 29-30 2.5
14-15 6.2 30-31 3.0 4.9 5.0

14-16 6.0 31-32 3.1 24

Note: Values are in km
15-16 3.8
Link Estimated Link Estimated
Distance (km) Distance (km) SHORTEST PATH METHOD
1-2 3.4 16-17 3.3 (Buenavista as Center Node)
1-5 2.8 17-19 10.0 5.9
2.1 13
1-17 12.4 18-19 4.0 12 4.9
11 2.7 10
1-18 10.2 18-21 8.3 3.7 3.3 14
9 1.6
1-32 8.9 19-20 8.2 8 6.2
4.4 3.1
6 1.2 6.0
2-3 2.0 20-21 1.0 7
2.5 6.0 15 16
2-4 5.1 21-22 3.0 5 4.6 3.8
2.8 Buenavista 3.3
5-6 2.5 22-23 2.9
3.4 12.4
2.0 1
5-7 4.6 22-28 4.4 3 2 17
6-8 4.4 23-24 5.0 5.1 10.2
7-8 1.2 23-26 2.0
4 8.9 10.0
7-9 3.1 26-28 3.3
7-15 6.0 24-25 4.9 3.1
31 32 18 4.0
3.0
8-11 3.7 25-26 2.4 3.8 19
9-10 1.6 25-27 3.5 2.5 30
28 8.3
9-11 3.3 26-27 2.4 29 3.4 4.4 8.2
10-12 2.7 26-28 3.3 27 2.4 3.3

11-12 2.1 28-32 3.8 3.5 26 2.0 22 3.0

12-13 5.9 27-30 3.4 2.4 23 2.9 21 20
25 1.0
13-14 4.9 29-30 2.5
14-15 6.2 30-31 3.0 4.9 5.0

14-16 6.0 31-32 3.1 24

Note: Values are in km
15-16 3.8
 Application to Actual Road Network

Siquijor Provincial Hospital

Lazi Community
Hospital

Shortest Path to the Hospitals, Siquijor Island Province

 Missing
road link

Base case: Complete road Scenario 1: One road link

network missing

2 Missing
road links

Scenario 2: Two road links

missing
Estimated Market Threshold of Public Markets/Talipapa, Siquijor Island
- Shortest path (distance) method
END