Network Flow Models Essays

Submitted By Renata-Balogh
Words: 925
Pages: 4

Network Flow Models
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