NETWORK ANALYSIS
Presented by:
E. Veera Pratap
Assistant Professor
Dept. of Mechanical Engineering
INTRODUCTION
• Network analysis finds great importance in electrical circuits,
pipelines, mobiles, roads, railways, airlines, resource
management, distribution, planning, scheduling, and
controlling of research and development projects.
• There are three types of network techniques:
• Shortest route problems
• Minimal spanning tree models
• Maximum flow problems
N O TAT I O N S U S E D I N N E T W O R K I N G
• Graphs:
• A graph G is a collection of vertices that
may or may not be connected to each
other by edges.
• Graph G is a set of points (called
vertices denoted by v) and connected
by lines (called edges denoted by e).
• For example, a graph with
• 6 vertices, v = (v1, v2, and v3, v4, v5, v6)
and
• 8 edges, e = (e1,e2,e3,e4,e5,e6,e7,e8)
Source: Operations research by Yadav and Malik
NOTATIONS USED IN
NETWORKING
• A graph G is said to be a
weighted graph when
weights are assigned to each
edge.
SHORTEST ROUTE PROBLEMS
• The determination of the shortest route from the origin to
destination in a network is known as the shortest route
problem.
• For solving the problem of determining the minimum path,
• Dijkstra’s Algorithm
• Floyd’s Algorithm
For example, if the vertices of the graph represent cities and edge weigh
Represent driving distances between pairs of cities connected by a direct
DIJKSTRA’S Road, Dijkstra’s algorithm can be used to find the shortest route between
ALGORITHM Two cities.
Input:
• Dijkstra’s Algorithm is a
Weighted graph G={E,V} and source vertex, such that all edge weights a
solution to the single source
non-negative.
shortest path problem in
graph theory.
Output:
• Works on both directed and
Lengths of shortest paths from a given source vertex to all other vertices
undirected graphs.
However, all edges must
have non-negative weights.
DIJKSTRA’S ALGORITHM
DIJKSTRA’S ALGORITHM
If d[u] + c(u,v) < d[v]
then d[v] = d[u]+c(u,v)
DIJKSTRA’S ALGORITHM
EXAMPLE
Find the shortest route in the network shown in
below figure.
C
4 5
A 1 D
2 B 7
DIJKSTRA’S ALGORITHM
EXAMPLE
Vertices A B C D C
4 5
Initialize 0 ♾ ♾ ♾
A 1 D
2 B 7
If d[u] + c(u,v) < d[v]
then d[v] = d[u]+c(u,v)
DIJKSTRA’S ALGORITHM
C
EXAMPLE 4 5
A 1 D
Vertices A B C D 2 B 7
Initialize 0 ♾ ♾ ♾
A(0) 2 4 ♾
If d[u] + c(u,v) < d[v]
then d[v] = d[u]+c(u,v)
DIJKSTRA’S ALGORITHM
EXAMPLE C
4 5
A 1 D
Vertices A B C D 2 B 7
Initialize 0 ♾ ♾ ♾
A(0) 2 4 ♾
B(2) 3 9
If d[u] + c(u,v) < d[v]
then d[v] = d[u]+c(u,v)
DIJKSTRA’S ALGORITHM
EXAMPLE C
4 5
A 1 D
Vertices A B C D 2 B 7
Initialize 0 ♾ ♾ ♾
A(0) 2 4 ♾
B(2) 3 9
C(1) 8
If d[u] + c(u,v) < d[v]
then d[v] = d[u]+c(u,v)
DIJKSTRA’S ALGORITHM
EXAMPLE C
4 5
A 1 D
Vertices A B C D 2 B 7
Initialize 0 ♾ ♾ ♾
A(0) 2 4 ♾
B(2) 3 9
C(1) 8
D(5) 8
If d[u] + c(u,v) < d[v]
then d[v] = d[u]+c(u,v)
DIJKSTRA’S
ALGORITHM
EXAMPLE 1
Source: https://www.slideshare.net/mansabMIRZA1/dijkstra-s-algorithm-627
DIJKSTRA’S ALGORITHM EXAMPLE 1 SOLUTION
Vertices s a b c d
Initialize 0 ♾ ♾ ♾ ♾
s 2 7 ♾ ♾
a 5 10 7
b 6 7
c 7
d 7
DIJKSTRA’S
ALGORITH
M
EXAMPLE 1
SOLUTION
Find the shortest route in the network shown below.
Determine the shortest path and shortest distance for below network.
DIJKSTRA’S
ALGORITHM
EXAMPLE 2
ce: https://www.slideshare.net/mansabMIRZA1/dijkstra-s-algorithm-62735754
D I J K S T RA ’ S A L G O R I T H M E X A M P L E 2
Vertices A B C D E F G H
Initialize
0 ♾ ♾ ♾ ♾ ♾ ♾ ♾
A (0)
8 2 5 ♾ ♾ ♾ ♾
C (2)
8 4 7 ♾ ♾ ♾
D (4)
6 5 10 7 ♾
E (5)
6 10 6 ♾
B (6)
10 6 ♾
G (6)
8 12
F (8)
11
H
11
D I J K S T RA ’ S A L G O R I T H M E X A M P L E 2
Vertic
A B C D E F G H
es
Initializ
0 ♾ ♾ ♾ ♾ ♾ ♾ ♾
e
A (0) 8 2 5 ♾ ♾ ♾ ♾
C (2) 8 4 7 ♾ ♾ ♾
D (4) 6 5 10 7 ♾
E (5) 6 10 6 ♾
B (6) 10 6 ♾
G (6) 8 12
F (8) 11
H 11
Determine shortest distance and shortest path from A to D for above problem.
Vertic
A B C D E F G H
es
Initiali
0 ♾ ♾ ♾ ♾ ♾ ♾ ♾
ze
A (0) 8 2 5 ♾ ♾ ♾ ♾
C (2) 8 4 7 ♾ ♾ ♾
D (4) 6 5 10 7 ♾
E (5) 6 10 6 ♾
B (6) 10 6 ♾
G (6) 8 12
F (8) 11
H 11
Determine shortest distance and shortest path from A to D for above problem.
Shortest distance: 4
Shortest path: AC Vertic
A B C D E F G H
es
A-C, C-D Initiali
0 ♾ ♾ ♾ ♾ ♾ ♾ ♾
2+2 = 4 ze
A (0) 8 2 5 ♾ ♾ ♾ ♾
C (2) 8 4 7 ♾ ♾ ♾
D (4) 6 5 10 7 ♾
E (5) 6 10 6 ♾
B (6) 10 6 ♾
G (6) 8 12
F (8) 11
H 11
Determine shortest distance and shortest path from A to F for above problem.
Vertices A B C D E F G H
Initialize 0 ♾ ♾ ♾ ♾ ♾ ♾ ♾
A (0) 8 2 5 ♾ ♾ ♾ ♾
C (2) 8 4 7 ♾ ♾ ♾
D (4) 6 5 10 7 ♾
E (5) 6 10 6 ♾
B (6) 10 6 ♾
G (6) 8 12
F (8) 11
H 11
Determine shortest distance and shortest path from A to F for above problem.
Shortest distance: 8
Shortest path: Vertic
A B C D E F G H
FGEDCA es
ACDEGF Initiali
0 ♾ ♾ ♾ ♾ ♾ ♾ ♾
ze
A-C, C-D, D-E, E-G, G-F A (0) 8 2 5 ♾ ♾ ♾ ♾
2+2+1+1+2=8
C (2) 8 4 7 ♾ ♾ ♾
D (4) 6 5 10 7 ♾
E (5) 6 10 6 ♾
B (6) 10 6 ♾
G (6) 8 12
F (8) 11
H 11
DIJKSTRA’S
ALGORITHM
EXAMPLE 3
Source: operations research by panneerselvam
DIJKSTRA’S
ALGORITHM
EXAMPLE 4
Source: operations research by panneerselvam
DIJKSTRA’S ALGORITHM EXAMPLE 5
Find the shortest route in the network shown below.
Ans: 1-3-4-6, 10
Find the shortest route in the network shown below.
DIJKSTRA’S
ALGORITH
M EXAMPLE
6
FLOYD’S ALGORITHM
• Floyd’s algorithm (or) All pairs shortest path is used to find the shortest path and
the corresponding distance from any source to any destination node in a given
distance network.
• Steps:
• Firstly, we initialize the solution matrix same as the input graph matrix.
• Then we update the solution matrix by considering all vertices as an
intermediate vertex.
• The idea is to one-by-one pick all vertices and updates all shortest paths which
include the picked vertex as an intermediate
)+ )] vertex in the shortest path.
FLOYD’S ALGORITHM EXAMPLE
Consider the following directed weighted graph-
Using Floyd Warshall Algorithm,
find the shortest path distance between
every pair of vertices.
urce: https://www.gatevidyalay.com/floyd-warshall-algorithm-shortest-path-algorithm/
FLOYD’S ALGORITHM EXAMPLE
2 is intermediate support 4 is intermediate support
2
1 1 1
1 3
2 3 3 2 4 2
4
4 4 3
1 is intermediate support
3 is intermediate support
FLOYD’S ALGORITHM EXAMPLE
Step 1:
•Remove all the self loops and parallel edges (keeping the lowest weight edge) from the graph.
•In the given graph, there are neither self edges nor parallel edges.
Step 2:
•Write the initial distance matrix.
•It represents the distance between every pair of vertices in the form of given weights.
•For diagonal elements (representing self-loops), distance value = 0.
•For vertices having a direct edge between them, distance value = weight of that edge.
•For vertices having no direct edge between them, distance value = ∞.
FLOYD’S ALGORITHM
EXAMPLE
•Step 2:
•Write the initial distance matrix.
•It represents the distance between every pair of vertices in
the form of given weights.
•For diagonal elements (representing self-loops), distance
value = 0.
•For vertices having a direct edge between them, distance
value = weight of that edge.
•For vertices having no direct edge between them, distance
value = ∞.
•Initial distance matrix for the given graph is-
)+ )]
1 is intermediate support
)+ )] 𝑑1 ( 3 , 2 )=𝑀𝑖𝑛 [ ♾, 4 +8 ] =12
)+ )] 𝑑1 ( 3 , 4 )= 𝑀𝑖𝑛 [ ♾, 4 +1 ] =5
FLOYD’S ALGORITHM EXAMPLE
2 is intermediate support
)+ )] 𝑑2 ( 1 ,3 )=𝑀𝑖𝑛 [ ♾, 8+1 ] =9
)+ )] 𝑑2 ( 4 , 3 ) =𝑀𝑖𝑛 [ 9 , 2+1 ] =3
FLOYD’S ALGORITHM EXAMPLE
3 is intermediate support
FLOYD’S ALGORITHM EXAMPLE
4 is intermediate support
FLOYD’S ALGORITHM EXAMPLE
Apply Floyd’s algorithm to it and generate the final distance matrix.
FLOYD
ALGORITHM
EXAMPLE
F LOY D A L GOR I T H M
E XA M P L E
S OLU T I ON
F LOY D A L GOR I T H M
E XA M P L E
S OLU T I ON
FLOYD
ALGORITHM
EXAMPLE
SOLUTION
FLOYD’S
ALGORITHM
EXAMPLE
a. Apply Floyd’s algorithm to it and generate the final distance matrix.
b. Find the shortest path and the corresponding distance from the source
Node to the destination node as indicated in each of the cases: 1-6, 5-1 a
urce:
erations Research by pannerselvam
FLOYD’S ALGORITHM
EXAMPLE SOLUTION
FLOYD’S
ALGORITHM Intermediate
vertex is 1
EXAMPLE
SOLUTION Min((2,3), (2,1)+(1,2))
FLOYD’S
ALGORITHM
EXAMPLE
SOLUTION
FLOYD’S
ALGORITHM
EXAMPLE
SOLUTION
FLOYD’S
ALGORITHM
EXAMPLE
SOLUTION
FLOYD’S
ALGORITHM
EXAMPLE
SOLUTION
FLOYD’S
ALGORITHM
EXAMPLE
SOLUTION
FLOYD’S ALGORITHM
EXAMPLE SOLUTION
Find the shortest path and the corresponding
distance from the source node to the destination
node as indicated in each of the cases: 1-6, 5-1
and 5-2.
Sol:
Shortest path from node 1 to node 6 is 1-3-5-6
and corresponding distance = 8.
Node 5 to node 1 is 5-3-1, distance =7
Node 5 to node 2 is 5-3-4-2, distance =7
Source:
https://web.mit.edu/urban_or_book/www/book/chapter6/6.2.2.html
FLOYD’S ALGORITHM
EXAMPLE
FLOYD’S ALGORITHM
EXAMPLE
FLOYD’S ALGORITHM
EXAMPLE SOLUTION
FLOYD’S ALGORITHM
EXAMPLE SOLUTION
FLOYD’S ALGORITHM
EXAMPLE SOLUTION
FLOYD’S ALGORITHM
EXAMPLE SOLUTION
FLOYD’S ALGORITHM
EXAMPLE SOLUTION
Find the shortest routes between every two nodes. By using Floyd’s Algorithm
MINIMAL SPANNING
TREE
• What is spanning tree?
• A spanning tree is a subset of Graph G, which has all the
vertices covered with minimum possible number of edges.
Hence, a spanning tree does not have cycles and it cannot be
disconnected.
• We found three spanning trees off one complete graph. A
complete undirected graph can have maximum nn-2 number of
spanning trees, where n is the number of nodes. In the above
addressed example, n is 3, hence 33−2 = 3 spanning trees are
possible.
MINIMAL SPANNING TREE
• In a weighted graph, a minimum spanning tree is a
spanning tree that has minimum weight than all other
spanning trees of the same graph. In real-world
situations, this weight can be measured as distance,
traffic load or any arbitrary value denoted to the edges.
MINIMUM SPANNING-TREE
ALGORITHM
• We shall learn about two most important spanning tree
algorithms here −
• Prim's Algorithm
• Kruskal's Algorithm
Construct the minimum spanning tree (MST) for the given
graph using Prim’s Algorithm-
PRIM’S
ALGORITHM
PRIM’S ALGORITHM
PRIM’S
ALGORITHM
PRIM’S
ALGORITHM
STEP 6
PRIM’S
ALGORITHM
PRIM’S
ALGORITH
M
Prim's algorithm to find
minimum cost spanning
uses the greedy
approach.
Source:
https://www.tutorialspoint.com/data_structures_algorithms/prims_spanning_tree_algorithm
PRIM’S
ALGORITHM
• Step 2 - Choose any arbitrary node as root node
• In this case, we choose S node as the root node of Prim's
spanning tree. This node is arbitrarily chosen, so any
node can be the root node. One may wonder why any
video can be a root node.
PRIM’S
• So the answer is, in the spanning tree all the nodes of a
ALGORITHM
graph are included and because it is connected then
there must be at least one edge, which will join it to the
rest of the tree.
PRIM’S
ALGORITHM
PRIM’S
ALGORITHM
PRIM’S
ALGORITHM
PRIM’S
ALGORITHM
PRIM’S
ALGORITHM
•Construct the minimum
spanning tree (MST) for
the given graph using
Prim’s Algorithm-
PRIM’S ALGORITHM
•Construct the minimum spanning tree (MST) for
the given graph using Prim’s Algorithm-
PRIM’S
ALGORITHM
PRIM’S ALGORITHM
•Construct the minimum spanning tree (MST) for the given graph using Prim’s Algorithm-
PRIM’S ALGORITHM
KRUSHKAL’S
ALGORITHM
EX-1
Kruskal's algorithm to find the minimum
cost spanning tree uses the greedy
approach.
Source:
https://www.tutorialspoint.com/data_structur
es_algorithms/kruskals_spanning_tree_algori
thm.htm
KRUSHKAL’S
ALGORITHM
KRUSHKAL’S
ALGORITHM
KRUSHKAL’S
ALGORITHM
KRUSHKAL’S
ALGORITHM
KRUSHKAL’S
ALGORITHM
KRUSHKAL’S
ALGORITHM
KRUSHKAL’S
ALGORITHM
KRUSHKAL’S
ALGORITHM
EX-2
KRUSHKAL’S
ALGORITHM
The final minimum spanning tree obtained from the given weighted grap
by using Kruskal's algorithm is -
KRUSHKAL’S
ALGORITHM
KRUSHKAL’S
ALGORITHM
EX-4
KRUSHKAL’S
ALGORITHM
KRUSHKAL’S
ALGORITHM
KRUSHKAL’S
ALGORITHM
KRUSHKAL’S
ALGORITHM
DIFFERENCE
Ford and Fulkerson algorithm
MAXIMUM
FLOW
PROBLEM
S
Flow – Source to Sink
How much flow can we push through the network
given that each edge has a certain capacity?
Ford and Fulkerson algorithm
MAXIMUM
FLOW
PROBLEM
S
Ford and Fulkerson algorithm
MAXIMUM
FLOW
PROBLEM
S
Ford and Fulkerson algorithm
MAXIMUM
FLOW
PROBLEM
S
S-v2-v4-t : 6
Flow/capacity
MAXIMUM FLOW PROBLEMS
Ford and Fulkerson algorithm
S-v2-v4-t : 6
Residual capacity = original capacity - flow
S-v1-v3-t : 3
MAXIMUM FLOW PROBLEMS
Ford and Fulkerson algorithm
S-v2-v4-t : 6
S-v1-v3-t : 3 Every
Flow = 11 vertex should have same inflow and outflow
S-v1-v4-t : 2
MAXIMUM FLOW PROBLEMS
Ford and Fulkerson algorithm
S-v2-v4-t : 6
S-v1-v3-t : 3 Every
Flow = 12 vertex should have same inflow and outflow
S-v1-v4-t : 2
S-v1-v4-v2-v3-t : 1
Consider:
Non full forward edge
Non zero backward edge
MAXIMUM FLOW PROBLEMS
S-v2-v4-t : 6
S-v1-v3-t : 3 Every
Flow = 12 vertex should have same inflow and outflow
S-v1-v4-t : 2
S-v1-v4-v2-v3-t : 1
MAXIMUM FLOW PROBLEMS
Ford and Fulkerson algorithm
FORD AND FULKERSON ALGORITHM
FORD AND FULKERSON ALGORITHM
FORD AND FULKERSON ALGORITHM
FORD AND FULKERSON ALGORITHM
FORD AND FULKERSON ALGORITHM
FORD AND FULKERSON ALGORITHM
FORD AND FULKERSON ALGORITHM
FORD AND FULKERSON ALGORITHM
Flow/capacity
FORD AND FULKERSON ALGORITHM
Flow/capacity
FORD AND FULKERSON ALGORITHM
Flow/capacity
FORD AND FULKERSON ALGORITHM
Flow/capacity
FORD AND FULKERSON ALGORITHM
Flow/capacity No path from source to sink
FORD AND FULKERSON ALGORITHM
Flow/capacity
Augmented path : Bottleneck
capacity
S-v-t : 3
S-w-t : 3
S-u-z-t : 2
S-v-w-t : 1
S-u-w-z-t : 1
Maximum flow -10
FORD AND FULKERSON ALGORITHM
Flow/capacity
FORD AND FULKERSON ALGORITHM
Flow/capacity
Augmenting path Bottle neck capacity
0-1-3-5 12
0-2-4-5 4
0-2-4-3-5 7
Thank you
