Network Flow Models Essays

Submitted By Renata-Balogh
Words: 925
Pages: 4
Open Document
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
Show More

Related Documents: Network Flow Models Essays

Essay about Brs Mdm3 Tif Ch05

Assignment, and Network Models 5.1 Chapter Questions 1) Which of the following is NOT a network flow model? A) Transportation model B) Assignment model C) Product mix model D) Shortest-path model E) Minimal-spanning tree model Answer: C Page Ref: 162 Topic: Introduction Difficulty: Easy 2) Which of the following models determines the path through the network that connects all the points? A) Transportation model B) Assignment model C) Product mix model D) Shortest-path model E) Minimal-spanning…

Words 1878 - Pages 8

Cash Flow and supply Chain Modeling Essay

Network Design in a Supply Chain Facility Location Models MGO 636 Supply Chain Modeling Design & Optimization 1 Outline • Background • Major Factors & Framework • Network Design Models – Plant Location Model – Demand Allocation Model – Plant Location Model with Multiple Sourcing – Plant Location Model with Single Sourcing MGO 636 Supply Chain Modeling Design & Optimization 2 Distribution Network: Plant, DC, Warehouse Customer DC MGO 636 Supply Chain Modeling Design & Optimization 3 Network…

Words 2664 - Pages 11

computer model Essay

Logical model that shows different Layers The Layers The OSI, or Open System Interconnection, model defines a networking framework to implement protocols in seven layers. This article explains the 7 Layers of the OSI Model. The OSI, or Open System Interconnection, model defines a networking framework to implement protocols in seven layers. Control is passed from one layer to the next, starting at the application layer in one station, and proceeding to the bottom layer, over the channel to the…

Words 618 - Pages 3

Which Of The Following Is True About A TCP/IP Security Standards?

Multiple Choice Questions 1. Which of the following is true about a TCP/IP network? The network uses standards defined in TCP/IP RFC's plus other standards. 2. Which of the following terms is not a common synonym for TCP/IP model? Ethernet / TCP/IP Mapping 3. Think generically about the idea of a networking standard, ignoring any particular standard or standards group. Which of the following is typically true of a standard? It exists as a written document / it has been passed through…

Words 1024 - Pages 5

wireless data center network Essay

ON PARALLEL AND DISTRIBUTED SYSTEMS, VOL. 24, NO. 12, DECEMBER 2013 2365 Dynamic Scheduling for Wireless Data Center Networks Yong Cui, Member, IEEE, Hongyi Wang, Xiuzhen Cheng, Senior Member, IEEE, Dan Li, Member, IEEE, and Antti Yla¨-Ja¨a¨ski Abstract—Unbalanced traffic demands of different data center applications are an important issue in designing data center networks (DCN). In this paper, we present our exploratory investigation on a hybrid DCN solution of utilizing wireless transmissions…

Words 8908 - Pages 36

Simulation For Multi Echelon Inventory System

Simulation for Multi Echelon Inventory System 1. Background: A supply chain system is a network that mediates the flow of entities involved in a product life cycle from production to vending. Such a network consists of nodes and arcs. Nodes represent suppliers, manufacturers, distributors and vendors (e.g. retail stores) as well as their inventory facilities for storing products and transportation facilities for shipping them among nodes. Arcs represent routes connecting the nodes along which…

Words 795 - Pages 4

ntc405 week4 assign Essay examples

and timely delivery of network communications between two hosts. Some of the services provided by TCP are sequencing of data packets, flow control, and error checking. Internet Protocol (IP), the lower layer, handles the address part of each packet so that it gets to the right destination (Rounse, nd). Using the client/server modes, each gateway computer on the network checks this address to see where to forward the message. The Open Systems Interconnection (OSI) model is a theoretical way of…

Words 738 - Pages 3

OSI model Essay

Objectives What is the purpose of a Network model? What are the layers of the OSI model? What are the characteristics of each layer of the OSI model? How does the TCP/IP stack compare to the OSI model? What are the well-known TCP and/or UDP port numbers for a given collection of common applications The Purpose of Reference Models It breaks network communication into smaller, simpler parts that are easier to develop. It facilitates standardization of network components to allow multiple-vendor…

Words 927 - Pages 4

2nd Ed Ch1 VA 090831rs Essay

Communications and Network Management Overview Network Management: Principles and Practice © Mani Subramanian 2010 1 Chapter 1 Overview Data Communications and NM Objectives • Telecommunications overview  Data communications overview  Evolution of converged networks  Desktop processors and LAN technology  Client-Server architecture in networking  Internet and intranet  Network communication protocols  OSI and Internet standards  Broadband networks and services  Need for network management…

Words 2522 - Pages 11

Engineer: Transmission Control Protocol and Tcp Connection Management Essay

would flow unhindered between network devices.  There would be no need for protocol layers as there would be no:  Bit errors  Congestion  Need for alternate routing  Problems in determining destinations  Security issues Layered Protocols (1a)  Layers in the OSI model. 2-1 Layered Protocols (1b)  Who does what in the OSI model. 2-1 Applications (FTP, SMTP, etc) Not used Not used End to end connection (TCP & UDP) Addressing, accounting & routing Framing, flow control…

Words 683 - Pages 3