Lecture_23_Network models : Shortest Route Problem

23.1 Shortest Route Problem
The criterion of this method is to find the shortest distance between two nodes with minimal
cost.
Example 1
Find the shortest path
Solution
n
Solved nodes
directly
connected to
unsolved
nodes
Closest
connected
unsolved
node
Total distance
involved
nth nearest
node
Minimum
distance
Last
connection
1 a c 7 c 7 a-c
2 a
c
b
e
13
7+6 =13
b
e
13
13
a-b
c-e
3
b
c
e
d
f
h
13+5 =18
7+11 =18
13+8 =21
d
f
-
18
18
-
b-d
c-f
-
4
e
d
f
h
g
h
13+8 =21
18+9 =27
18+5 =23
h
-
-
21
-
-
e-h
-
-
5
e
h
d
g
i
g
13+10 =23
21+10 =31
18+9 =27
g
-
-
23
-
-
e-g
-
-
6 g
h
i
i
23+6 =29
21+10 =31
i
-
29
-
g-i
-
Lecture 23
Network models : Shortest Route Problem
1
The shortest path from a to i is a ? c ?e ?g ? i
Distance = 7 + 6 + 10 + 6 = 29 units
Example 2
Solution
n
Solved nodes
directly
connected to
unsolved
nodes
Closest
connected
unsolved
node
Total
distance
involved
nth nearest
node
Minimum
distance
Last
connection
1 1 3 1 3 1 1-3
2 1
3
2
2
5
1+2 =3
-
2
-
3
-
3-2
3 2
3
5
4
3+1 =4
1+6 =7
5
-
4
-
2-5
-
4 2
3
6
4
3+6 =9
1+6 =7
-
4
-
7
-
3-4
2
5 4 4+3 =7 4 7 5-4
5
2
4
5
6
6
6
3+6 =9
7+4 =11
4+5 =9
6
-
6
9
-
9
2-6
-
5-6
6
4
5
6
7
7
7
7+6 =13
4+9 =13
9+2 =11
-
-
7
-
-
11
-
-
6-7
The shortest path from 1 to 7 can be
1 ?3 ? 2 ? 6 ?7
Total distance is 11 units
1 ? 3 ? 2 ?5 ? 6 ?7
Total distance = 11 units
3