Shortest Route
seeks the shortest route between
A chosen start point
A chosen destination
Minimal Spanning
Seeks the shortest route between all the points in a
network
Maximal flow
Determine maximum amount of flow ( vehicles, messages,
fluid...) that can enter and exit a network system in a given period of time.
Network Network Flow Models
Arrangement or series of connected paths
Haulage routes, train networks etc
Nodes
Represent junction points
Arcs
Connect the nodes
Represent flows
1
2
Short route problem
Shortest paths between pairs of nodes in a
network
Example
Brunei Government Development Agency
(GDA)
Multiple development projects
One central HQ for GDA – some projects
50+km
How to minimise costs of daily transport of people and materials
Shortest Route Algorithm
7
17
6
2
5
6
6
15
4
4
3
5
1
START
2
4
10
3
GDA HQ at
Node 1, other nodes are the project locations, numbers are distances in
Example : node 4 possible routes 1–2–4
1 -3–5–4
1–2–7–4
And many more!
Shortest Route Algorithm
7
17
6
[15,1]
2
5
6
6
15
4
4
3
2
5
[0,S]
1
START
4
10
3
[10,1]
Labelling: numbers in brackets: first no. = distance from previous node second no. = preceding node
Shortest Route Algorithm
7
17
6
[15,1]
2
5
6
6
15
4
4
3
5
[0,S]
[14,3]
1
START
2
4
10
3
[10,1]
Label can be tentative or permanent
Choose shortest route from node 1
= 10 km to node 3, make permanent
Permanent Label
Next stage starts from the previous
permanent label: in this case
3
5 , and
Nearest nodes2 are
Shortest Route Algorithm
7
17
[13,3]
6
[15,1]
2
5
6
6
15
4
4
3
5
[0,S]
[14,3]
1
START
2
4
10
3
[10,1]
Relabel node with shortest route from 1 via 3 and make permanent
Permanent Label
Next stage starts from the previous
permanent label: in this case
2
Nearest non permanently labelled
4 nodes
7
are
, and
Shortest Route Algorithm
[30,2]
7
17
[13,3]
6
2
5
6
6
[19,2]
15
4
4
3
5
[0,S]
[14,3]
1
START
2
4
10
3
[10,1]
From the tentatively labelled select the one with the lowest distance value: 5 and permanently label
Permanent Label
Shortest Route Algorithm
[30,2]
7
17
[13,3]
6
2
5
6
15
4
3
6
[19,2]
4
[18,5]
5
[0,S]
[14,3]
1
START
2
[16,5]
4
10
3
[10,1]
Repeat the process
Permanent Label
Shortest Route Algorithm
[22,6]
7
17
[13,3]
6
2
5
6
6
15
4
3
4
[18,5]
5
[0,S]
[14,3]
1
START
2
[16,5]
4
10
3
[10,1]
All nodes permanently labelled Permanent Label
Shortest routes
Node
Shortest route from Node 1
Distance (km)
2
1-3-2
13
3
1-3
10
4
1-3-5-4
18
5
1-3-5
14
6
1-3-5-6
16
7
1-3-5-6-7
22
Shortest Route algorithm
Step 1
Assign node 1 permanent label: [0,S]
Step 2
Calculate tentative labels to nodes directly reached from [0,S]
Step 3
Make tentatively labelled node with smallest distance from previous permanent node permanent
Step 4
Consider nodes reachable form new permanent node. If node already has a tentative label then reset label if new route is less distance (distance being the sum of arcs from start node). If not labelled yet apply new tentative label (sum of arcs from start node). Node value equals preceding permanent node.
Revisit step 3: pick tentative label with lowest distance value and make permanent.
Step 5
Shortest route to any given node can