Module 3

Graph Theory
Study of Graphs
 Königsberg Bridge Problem

• The city of Königsberg in Prussia was set on both

sides of the Pregel River, and included two large
islands which were connected to each other and the
mainland by seven bridges.
• The problem was to
Starting at one land area, is it possible to walk across
all the bridges exactly once and return to the starting
land area?
• The islands could not be reached by any route other
than the bridges.
 - a historically noted problem in mathematics
- it was posed in 1736

• River has four land areas (A, B,C, D)

• Bridges are labeled a, b, c, d, e, f, g
 Königsberg Bridge Problem
• In 1736, Euler represented Königsberg bridge
problem as graph; Answered the question in the
negative.
• This marked (as recorded) the birth of graph theory.
Graphs

6
 Graph

• A graph G=(V,E) consists of a set of vertices

and edges, such that each edge is identified
with an ordered pair of vertices.

• Ie. G=(V,E) where

V={v1,v2…..} are called vertices
E={e1,e2…..} are called edges,
such that each edge ek is identified with an
ordered pair (vi, vj) of vertices.
 e1

v1 e3 v2

e5 v5
e4 e2

e7

v3 e6 v4

• The vertices vi, vj associated with edge ek are called end

vertices of ek.
• An edge having the same vertex as both its end vertices is called a
self loop (loop)
• If more than one edge is associated with a given pair of vertices ,that
edges are called parallel edges.

• Graph with five vertices and seven edges. Edge e1 is a self loop
• Edges e4 and e5 are parallel edges.

e1

v1 e3 v2

e5 e4 e2 v5
e7
v3 e6 v4
• A graph that has neither self-loop nor parallel edges is called a
simple graph.

v1 e3 v2

e1
e2

v3 e4 v4
• A graph with a finite number of vertices and edges is called
finite graph ,otherwise it is called infinite graph.
• Simple Graph
– A graph with out any self loops or parallel edges
v1 e3 v2
e4 e2 v5
e1
• pseudo graph v3 e5 v4

– A graph that contains self loops and parallel edges

e1
v1 e3 v2
e5 e4 e2 v5
e7
v e v
• Multi graph 3 6 4

– A graph which is permitted to have multiple edges (parallel

edges) between a pair of vertices.
 When a vertex vi is an end vertex of some edge ej, vi and ej are said
to be incident with each other.
 Edges e2,e6,e7 are incident with the vertex v4.
 Two non-parallel edges are said to be adjacent if they are incident
on a common vertex.
 Edges e2 and e7 are adjacent

e1

v1 e3 v2

e5 e4 e2 v5

e7
v3 e6 v4
 Two vertices are said to be adjacent if they are the end vertices of
the same edge.
 Vertices v4 and v5 are adjacent
 The number of edges incident on a vertex vi, with self-loop counted
twice is called the degree, d(vi) of vertex vi.
d(v1)=d(v3)=d(v4)=3, d(v2)=4, d(v5)=1

e1

v1 e3 v2

e5 e4 e2 v5

e7
v3 e6 v4
 A vertex having no incident edge is called an isolated vertex
 Vertex v5 is an isolated vertex
 Isolated vertex has degree zero.
 A vertex of degree one is called a pendant vertex .
 Vertex v3 is a pendant vertex
 Two adjacent edges are said to be in series if their common
vertex is of degree two
 Edges e3 and e5 incident on v1 are in series

e1

v1 e3 v2

e5 e2 .v5

v3 e4 v4
• A graph with out any edges is called a null
graph.
– A null graph with 5 vertices

.v2

.v3
.v1
.v5
.v4
• Complete graph
– A simple graph in which there exists an edge between every
pair of vertices.
– a complete graph with n vertices is represented as Kn.
– It is also known as universal graph or clique.
– The degree of every vertex in a complete graph with n
vertices(Kn) is n-1.
– Total number of edges in G is n(n-1)/2.
 Complete Graphs
• Denoted by Kn.
 Representation of Graphs
• Adjacency List
• Adjacency Matrix
• Incidence matrix
 Adjacency List Representation

Two vertices are said to be adjacent if they are the end vertices of the same edge.
 Adjacency matrix

– The adjacency matrix of a graph G with n vertices is

an n by n binary matrix X=[xij] such that
xij=1, if there is an edge between ith and jth vertices
xij=0, if there is no edge between them
– Also known as connection matrix
 v3
v2
e4 v4 e8

e3 e5
e1
v5 e7
e2

e6 v6
v1
V1 v2 v3 v4 v5 v6

V1 0 1 0 0 1 1
V2 1 0 0 1 1 0
V3 0 0 0 1 0 0
V4 0 1 1 0 1 1
V5 1 1 0 1 0 0
V6 1 0 0 1 0 0
 Matrix representation of graphs
• Incidence matrix
• Let G be a graph with n vertices , e edges.
• Define an n by e matrix A=[aij], whose n rows correspond to
the n vertices and the e columns correspond to the e edges, as
follows:
a ij=1, if j th edge ej is incident on ith vertex vi,
aij=0, otherwise
• Such a matrix A is called vertex-edge incident matrix
• The incidence matrix contains only two elements 0 and 1. such a
matrix is called a binary matrix or a (0,1) matrix.
 v3
a
h
v6
v2 e b
v4
f
g c

v1 d v5

a b c d e f g h
V1 0 0 0 1 0 1 0 0
V2 0 0 0 0 1 1 1 1
v3 0 0 0 0 0 0 0 1
v4 1 1 1 0 1 0 0 0
V5 0 0 1 1 0 0 1 0
V6 1 1 0 0 0 0 0 0
• Since every edge is incident on exactly two vertices,
each column (representing an edge )has exactly
two 1’s.
• The number of 1’s in each row equals the degree
of the corresponding vertex.
• A row with all zeros, therefore, represents an isolated
vertex
• Parallel edges in a graph produce identical columns
in incidence matrix.
• Walk
– An alternate sequence of vertices and edges, beginning and
ending with vertices, such that each edge is incident with the
vertices preceding and following it.
– In the following fig: v1 a v2 b v3 c v3 d v4 e v2 f v5 is a walk
v1

g a

v3
c
b v2

e
d f

h
v4
v5
 Vertices with which a walk begins and end is
called its terminal vertices.
Length of the walk is the number of edges in the
walk.
A walk in which terminal vertices are the same is
called a closed walk

Eg: v1 a v2 b v3 c v3
• Path
– If no vertex of the walk appears more than once, then the
walk is called a path.
• Eg: v1 a v2 b v3 d v4 is a path
• The number of edges in a path is called the length of a
path

v1

g a
v3
c
b v2

e
d f

h
v4
v5
• Circuit
– A walk which starts and ends at the same vertex.
– No repetition of edges in a circuit.
– Every vertex in a circuit is of degree 2.
Eg: v2 b v3 d v4 e v2 is a circuit
Cycle
A circuit that does not contain any repetition of vertices
except the starting and ending vertex is called a cycle.

v1

g a
c v3
b v2

e
d f

v4 h
v5
Cycles with 3 ,4,5,6 Vertices
 Wheels
• When an additional vertex is added to the
cycle Cn, for n>=3 and connect this new
vertex to each of the n vertices in Cn by
new edges , we obtain a Wheel.
• Let G=(V,E) be a directed graph.
• The incoming or in-degree of v is the number of edges in G
that are incident into v and is denoted by id(v).
• The outgoing or outdegree of v is the number of edges in G
that are incident from v and is denoted by od(v).

If the directed graph has one or more loops, each loop at a given
vertex v contributes a count of 1 to each of id(v) and od(v).
 What are the in-degrees and out-degrees of the vertices
a, b, c, d in this graph:
id(b) = 4
a od(b) = 2
id(a) = 1 b
od(a) = 2

id(d) = 2 id(c) = 0
od(d) = 1 d c od(c) = 2
 SUB GRAPHS
 A graph g is said to be a sub-graph of a graph G if all the vertices
and all the edges of g are in G, and each edge of g has the same
end vertices in g as in G.
 Every graph is its own sub graph
 A single vertex in a graph G is a sub-graph of G
 A single edge in G together with its end vertices is also a sub-
graph of G
 Fig (b) is one of the sub-graph of fig (a)

e1
v1 e3 v2 v2
e5 e4 e2 v5 e2 v5
e7 e7
v3 e6 v4 v4
fig (a)-Graph G Fig (b)- Graph g1
SPANNING SUBGRAPH OF A GRAPH

 Given a (directed or undirected) graph G=(V,E) .Let

G1=(V1,E1) be a subgraph of G . If V1=V, then G1
is called a spanning subgraph of G.
 Bipartite graph

 A graph G is called bipartite if its vertex set V can be

decomposed in to two disjoint subsets V1 and V2 such that
every edge in G joins a vertex in V1 with a vertex in V2.
COMPLETE BIPARTITE GRAPH
CHECK WHETHER G AND H ARE
BIPARTITE
 Regular Graph
 A graph G in which all vertices are of equal degree.
 If degree(v)=k for all vertices v, Then the graph is called k-
regular.
 Give an example of 3 Regular bipartite graph. Ans : K3,3
4 Regular graph
OPERATIONS ON GRAPHS
G1 =(V1, E1)
G2 =(V2, E2)
Union of G1 and G2= G3= G1 U G2 whose
vertex set V3= V1 U V2
Edge set E3= E1 U E2
Intersection of G1 and G2= G4= G1 ∩ G2
 Connected and disconnected graphs
• An undirected graph G is said to be connected if there is at least
one path between every pair of vertices in G, otherwise G is
disconnected.
• A disconnected graph contain two or more connected graphs
• Each of these connected sub graph is called a component.
• Eg fig (a) is a connected graph
• Eg: fig (b) is disconnected graph

v1 v1
c

g a g
v3 v3 v7
c b v2 b v2
e
a
e d f v8
d f
c
h v4 h
v4 v5 v5
v6

fig (a) fig (b)

 Connected and disconnected graphs
v1

g a
v3
c
b v2

e
d f

h
v4
v5
v1
c
fig (a)
g
v3 v7
b v2
e
a
d f v8

c
v4 h
v5
fig (b) v6
Connectedness in Directed Graphs
• A directed graph is strongly connected if there is a
path from a to b and from b to a whenever a and b
are vertices in the graph.
Weakly Connected graph
 Multigraph
• A graph which is permitted to have multiple edges (parallel
edges) between a pair of vertices.
• Multiplicity of a multigraph
• Multiplicity of edge (a,b) = 3
• ” (b,c) and (d,e) =2
• ” (e,d) =1
 e1

v1 e3 v2

e5 e4 e2 v5
e7
v3 e6 v4

No. of ODD degree and EVEN degree vertices?

• The Handshaking Theorem

• Sum of degrees of all vertices in a graph G is twice the

number of edges,
n
Σ degree(vi) = 2e v 1
i=1
g a

v3
c
b v2

e
d f

h
v4
v5
• The Handshaking Theorem

• Sum of degrees of all vertices in a graph G is twice the

number of edges,
n
Σ degree(vi) = 2e
i=1 v 1

g a
c v3
b v2

e
d f
• Sum of degrees = 2+4+5+3+2 =16
v4 h
• [Link] edges =8 v5

• Therefore 16 = 2*8
 Try the following Qn
• How many edges are there in a graph with 10
vertices each of degree six?
 Try the following Qn
• How many edges are there in a graph with 10
vertices each of degree six?

• Ans: 30 Edges
 Isomorphism
• Two graphs are said to be isomorphic (equivalent) if they
have identical behavior in terms of graphic theoretic
properties

• Two graphs G and G1 are said to be isomorphic if there is

a one to one correspondence between their edges and
vertices such that the incidence relationship is preserved.
• Two isomorphic graphs must have
1. The same number of vertices
2. The same number of edges
3. An equal number of vertices with a given degree.
4. The incidence relationship must be preserved.
Isomorphic Graphs or not?
Isomorphic Graphs or not?
 Planar graphs
• A graph G is said to be planar if there exists some geometric
representation of G which can be drawn on a plane such that no
two of its edges intersect.

• A graph that can not be drawn on a plane with out a cross over
between its edges is called non-planar.

• A drawing of a geometric representation of a graph on any

surface such that no edges intersect is called embedding.

• To declare a graph G is non-planar , we have to show that of all

possible geometric representations of G none can be embedded
in a plane.

• An embedding of a planar graph G on a plane is called a plane

representation of G.
 Drawings in the plan

• Can a graph be drawn in a plane without edge crossings?

 Kuratowski’s two graphs
• The complete graph of five vertices (K5) is non-planar.
Proof:
• Kuratowski’s second graph ( K3,3 )is also non-planar.
– A regular connected graph with 6 vertices and 9 edges .

or
 Properties of kuratowski’s two graphs

1. Both are regular graphs

2. Both are non-planar
3. Removal of one edge or a vertex makes each a planar
graph
4. Kuratowski’s first graph is the non-planar graph with the
smallest number of vertices, and Kuratowski’s second
graph is the non-planar graph with smallest number of
[Link] both are the simplest nonplanar graphs.
 A plane representation of graph divides the plane into regions
called faces . Note: the outside area of a graph also counts as
a region.
2 Types of regions.
Finite region
– The area bounded by a subset of the vertices and edges of a
graph.
Infinite region:
– The portion of a plane lying outside a graph embedded in a
plane is called infinite region (outer or exterior region)
• Euler’s formula
A connected planar graph with n vertices and e edges
has e - n+2 regions. ie,
[Link] regions r = e – n + 2
Examples of Counting Regions
Count [Link] Regions

5
1
2 4

3
6
 Cut-set
• In a connected graph G, a cut-set is a set of edges whose
removal from G will disconnect the graph G, provided
removal of no proper subset of these edges disconnects
G.
• A cut –set is a minimal disconnecting set of edges.
Whenever a cut-set for a connected graph consists of
only one edge, that edge is called a bridge for the
graph.
– Eg: Different cut-sets are
{a,c,d,f},
{a,b,g} ,
{a,b,e,f},
{d,h,f} and
{k} .
The set {a,c,h,d} is not a cut set, because one of its
proper subset {a,c,h} is a cut-set.
• Edge connectivity:
– The number of edges in the smallest cut-set (cut-set with
fewest number of edges) is called the edge connectivity of G.

• Vertex connectivity:
– Vertex connectivity of a connected graph G is defined as the
minimum number of vertices whose removal from G leaves the
remaining graph disconnected.
Cut vertex
 Euler Circuit

• Euler Circuit
- A closed walk that includes all the edges in a graph exactly
once and starts and ends at the same vertex.
 A given connected graph G is an Euler graph if and only if all
vertices of G are of even degree
 Cut Edge

A cut edge in a graph is an edge whose

removal disconnects a component of the
graph.
 Example: Cut Edges

Identify the cut edges in the graph below.

B C H
F

A D E G
Solution
CE and GH are cut edges, if either is removed, it
would disconnect the graph.
 Fleury’s Algorithm
• Fleury’s algorithm can be used to find an Euler circuit in any
connected graph in which each vertex has even degree.
• Step 1: Start at any vertex. Go along any edge from this
vertex to another vertex. Remove this edge from the graph.
• Step 2: Choose any edge from this vertex, but not a cut
edge, unless one have no other option. Go along the chosen
edge. Remove this edge from the graph.
• Step 3: Repeat Step 2 until all the edges have used and
arrived at the vertex at which you started the walk.
 Example: Using Fleury’s Algorithm
Find an Euler circuit for the graph below.
B C
F

A D E
Solution
B C
Remove F
BC
A D E
© 2008 Pearson Addison-
Wesley. All rights reserved 15-2-78
 Example: Using Fleury’s Algorithm
Solution (continued)

B C
F
Remove
CF
A D E

B C
F
Remove
FD
A D E
© 2008 Pearson Addison-
Wesley. All rights reserved 15-2-79
 Example: Using Fleury’s Algorithm
Solution (continued)

B C
F
Remove
DE
A D E

Now it is clear to finish with

E  C  D  A  B.

© 2008 Pearson Addison-

Wesley. All rights reserved 15-2-80
 Example: Using Fleury’s Algorithm

The complete Euler circuit is

B  C  F  D  E  C  D  A  B.

Note that a graph that has an Euler circuit always

has more than one Euler circuit.

© 2008 Pearson Addison-

Wesley. All rights reserved 15-2-81
 Shortest-Path Problems
• Graphs that have a number assigned to each edge are called
weighted graphs.
• Weighted graphs are used to model computer networks.
• Length of a path in a weighted graph= sum of weights of
edges of the path.

• Find a shortest path between two vertices in a weighted graph?

• Dijkstra ’s Algorithm can be used when all edges are

assigned with a non-negative weight.
What is the length of the shortest path between a and zin the
following weighted graph?

AAAnswer:6 a->d->e->z
Using Dijkstra’s Algorithm find shortest path from a to z
Solution
 Euler Graph

 A closed walk in a graph G that contains all the

edges of the graph is called an Euler line.
 A graph that contain Euler line is called an Euler
graph
 In fig (a) : a closed walk v1 e4 v3 e1 v4 e2 v2 e3 v1 is an
Euler graph

v1 e3 v2

e4 e2

v3 e1 v4

Star of David Mohammed’s scimitars

 Hamiltonian paths and circuits
• Closed walk that traverses every vertex of G exactly once,
except the terminal vertices.
• A circuit in a connected graph G is said to be Hamiltonian if it
includes every vertex of G
• A Hamiltonian circuit in a graph of n vertices consists of
exactly n edges.

• If we remove any one edge from a Hamiltonian circuit, obtain

a path, this is called a Hamiltonian path. Hamiltonian path in a
graph G traverses every vertex of G.
• Every graph that has a Hamiltonian circuit also has a
Hamiltonian path.
• The length of a Hamiltonian path in a connected graph of n
vertices is n-1
 Hamiltonian circuits
• Closed walk that traverses every vertex of G exactly once,
except the terminal vertices is called a Hamiltonian Circuit.
• A Hamiltonian circuit in a graph of n vertices consists of
exactly n edges.

• If we remove any one edge from a Hamiltonian circuit, obtain

a path, this is called a Hamiltonian path. Hamiltonian path in a
graph G traverses every vertex of G.
• Every graph that has a Hamiltonian circuit also has a
Hamiltonian path.
• The length of a Hamiltonian path in a connected graph of n
vertices is n-1
Find a Hamiltonian Circuit
 Tutorial 6
Dijkstra's Shortest Path Algorithm
Find shortest path from s to t.

24
2 3
9

s
18
14
2 6
6
30 4 19
11
15 5
5
6
20 16

t
7 44

100
Draw 2 Hamiltonian Circuits
• Proofs
1.
Prove that K5 or K3,3. are not planar graphs.
– In a simple connected planar graph with r
regions, n vertices and e edges (e>2), the
following inequalities hold:
3r  2e
e  3n-6

Prove that K5 and K3,3 are nonplanar.

 K5 is non-planar
• n=5
• e= n * (n – 1) / 2 = 10
• Using second theorem of planar graphs:
• e <= 3n – 6
• 10 <= 3(5) – 6
• 10 <= 9 ???
• By contradiction, K5 must be non-planar

Note: Total number of edges in a complete graph G with n

vertices is n(n-1)/2
 Traveling salesman problem

A sales man is required to visits a number of cities during a trip.

Given the distance between the cities, in what order should he
travel so as to visit very city precisely once and return to the
home city, with minimum mileage traveled.
Representing the cities by vertices and the roads
between them by edges, we get a graph. In this graph, every
edge ei is associated with a real number ,(the distance in miles)
w(ei) . Such a graph is known as weighted graph.

In this problem, if each of the cities has a road to every other

city, we obtain a complete weighted graph. This graph has a
number of Hamiltonian circuits and we have to find one that
has the smallest sum of distance.
Starting from any vertex we have n-1 edges to choose from the
first vertex, n-2 from the second, n-3 from the third and so on.
Hence TSP is to find the shortest Hamiltonian circuit.
 A B C D E

A 0 14 12 7 10

B 14 0 9 13 5

C 12 9 0 6 8

D 7 13 6 0 11

E 10 5 8 11 0
 Some solutions for TSP
• Let the Starting city be A
A –D – C – E – B – A
distance=40

• Let the Starting city be C

C –D – A – E – B – C
distance=37
Theorem:
Number of vertices of odd degree in a graph is always even
Proof:
Let G be a graph with n vertices(v1, v2, v3,…..,Vn) and e edges.
Since we have
n
Σ d( vi) = 2e =even number
i=1
Among n vertices, let Vj vertices are even degree and Vk vertices are
odd degree.
n
Σ d( vi) = Σ d(vj) + Σ d( vk) = 2e
i=1 even odd

2e - Σ d(vj)= Σ d( vk) ,should be an even number.

even odd
Because each d(vk) is odd, the total number of terms in sum must be
even to make the sum an even number. Therefore the number of
odd vertices in G is even.
 v3
v2
e4 v4 e8

e3 e5
e1
v5 e7
e2

e6 v6
v1

3+3+1+3+4+2 = 2*8
 Euler’s formula
A connected planar graph with n vertices and e edges has e
- n+2 regions. ( that is, r = e – n + 2)
Proof:
Consider the planar graph G with n vertices and e edges. The
theorem can be proved by constructing a sequence of
subgraphs G1, G2, G3,…….Ge by successively adding an edge
at each stage. Arbitrarily pick one edge of G to obtain G1.
Obtain Gn from Gn-1 by adding an edge that is incident with
a vertex already in Gn-1. This construction is possible because
G is connected. G is obtained after e edges are added.
Let rn,en,and vn represent the number of regions, edges and
vertices of the planar representation of Gn. The relation
r1=e1-v1+2 is true for G1
The relation r1=e1-v1+2 is true for G2,because e1=1,v1=2, and
r1=1.
Now assume that rn=en-vn+2.
Let {an+1,bn+1}be the edge that is added to Gn to obtain Gn+1.
There are two possibilities to [Link] the first case, both
an+1 and bn+1 are already in [Link] two vertices must be
on the boundary of a common region R, or else it would be
impossible to add the edge{an+1,bn+1} to Gn without two
edges crossing( and Gn+1 is planar). The addition of this new
edge splits R into two regions. Consequently, in this case,
rn+1 =rn+1,
en+1=en+1and ,
Vn+1=Vn. The formula is still true.
In other words, rn+1=en+1-vn+1+2 is true.
In the second case, one of the two vertices of the new edge is not
already in Gn. Suppose that an+1 is in Gn but bn+1 is not. Adding
this edge does not produce any new regions , because bn+1
must be in the region that has an+1 on its boundary.
Consequently,
rn+1= rn. Moreover,
en+1= en+1 and
Vn+1= Vn+1. Here also formula remains the same and is true.
In other words rn+1= en+1-vn+1+2 is true.
Hence Euler’s Formula is true for all planar graphs.
For G1
r= e-n+2 = 0-1+2 = 1 region
For G2
r =2-n+2 = 1-2+2 =1 region

For G3
case1
r= 2-3+2 =1 region
Case 2
r= 3-3+2 =2 regions
• Theorem 2-4
A given connected graph G is an Euler
graph if and only if all vertices of G are of
even degree
Proof:
Suppose that G is an Euler Graph. It therefore
contains an Euler line (which is a closed walk). In
tracing this walk we observe that every time the walk
meets a vertex v it goes through two “new” edges
incident on v- with one vertex “entered” v and with
the other “exited”. This is true not only of all
intermediate vertices of the walk but also of the
terminal vertex, because we “exited and “entered” the
same vertex at the beginning and end of the walk,
respectively. Thus if G is an Euler Graph, the degree
of every vertex is even.
To prove the sufficiency of the condition, assume
that all vertices of G are of even degree. Now we
construct a walk starting at an arbitrary vertex v and
going through the edges of G such that no edge is
traced more than once. We continue tracing as far as
possible. Since every vertex is of even degree , we can exit
from every vertex we enter; the tracing cannot stop at any
vertex but v. And since v is also of even degree, we shall
eventually reach v when tracing comes to an end. If this closed
walk h we just traced includes all the edges of G, G is an
Euler graph.
 Ans
Find shortest path from s to t.
24
2 3
9

s
18
14
2 6
6
30 4 19
11
15 5
5
6
20 16

t
7 44

119
 Dijkstra's Shortest Path Algorithm
S={ }
PQ = { s, 2, 3, 4, 5, 6, 7, t }



24
2 3
0 9

s
18
14  2 6
6 
30  4 19
11
15 5
5
6
20 16

t
7 44
distance
120 label  
 Dijkstra's Shortest
S={ }
Path Algorithm
PQ = { s, 2, 3, 4, 5, 6, 7, t }

delmin


24
2 3
0 9

s
18
14  2 6
6 
30  4 19
11
15 5
5
6
20 16

t
7 44
distance
121 label  
 Dijkstra's Shortest
S={s}
Path Algorithm
PQ = { 2, 3, 4, 5, 6, 7, t }

decrease key


X
 9
24
2 3
0 9

s
18
14 X
 14 6
2
6 
30  4 19
11
15 5
5
6
20 16

t
7 44
distance
122 label  15
X 
 Dijkstra's Shortest
S={s}
Path Algorithm
PQ = { 2, 3, 4, 5, 6, 7, t }

delmin

X 9

24
2 3
0 9

s
18
14 X 14
 6
2
6 
30  4 19
11
15 5
5
6
20 16

t
7 44
distance
123 label  15
X 
 Dijkstra's Shortest
S = { s, 2 }
Path Algorithm
PQ = { 3, 4, 5, 6, 7, t }


X 9

24
2 3
0 9

s
18
14 X 14
 6
2
6 
30  4 19
11
15 5
5
6
20 16

t
7 44

124  15
X 
 Dijkstra's Shortest
S = { s, 2 }
Path Algorithm
PQ = { 3, 4, 5, 6, 7, t }

decrease key

X
 33
X 9

24
2 3
0 9

s
18
14 X 14
 6
2
6 
30  4 19
11
15 5
5
6
20 16

t
7 44

125  15
X 
 Dijkstra's Shortest
S = { s, 2 }
Path Algorithm
PQ = { 3, 4, 5, 6, 7, t }

X
 33
X 9

24
2 3
0 9
delmin
s
18
14 X 14
 6
2
6 
30  4 19
11
15 5
5
6
20 16

t
7 44

126  15
X 
 Dijkstra's Shortest
S = { s, 2, 6 }
Path Algorithm
PQ = { 3, 4, 5, 7, t }

32
X
 33
X
X 9

24
2 3
0 9

s
18
14 X 14
 6
2
6 
44
30 X
 4 19
11
15 5
5
6
20 16

t
7 44

127  15
X 
 Dijkstra's Shortest
S = { s, 2, 6 }
Path Algorithm
PQ = { 3, 4, 5, 7, t }

32
X
 33
X
X 9

24
2 3
0 9

s
18
14 X 14
 6
2
6 
44
30 X
 4 19
11
15 5
5
6
20 16

t
7 44

128  15
X delmin 
 Dijkstra's Shortest
S = { s, 2, 6, 7 }
Path Algorithm
PQ = { 3, 4, 5, t }

32
X
 33
X
X 9

24
2 3
0 9

s
18
14 X 14
 6
2
6 
X 35
44
30 X
 4 19
11
15 5
5
6
20 16

t
7 44

129  15
X 
59 X
 Dijkstra's Shortest
S = { s, 2, 6, 7 }
Path Algorithm
PQ = { 3, 4, 5, t } delmin

32
X
 33
X
X 9

24
2 3
0 9

s
18
14 X 14
 6
2
6 
X 35
44
30 X
 4 19
11
15 5
5
6
20 16

t
7 44

130  15
X 
59 X
 Dijkstra's Shortest
S = { s, 2, 3, 6, 7 }
Path Algorithm
PQ = { 4, 5, t }

32
X
 33
X
X 9

24
2 3
0 9

s
18
14 X 14
 6
2
6 
X 34
X 35
44
30 X
 4 19
11
15 5
5
6
20 16

t
7 44

131  15
X 51 59 
X X
 Dijkstra's Shortest
S = { s, 2, 3, 6, 7 }
Path Algorithm
PQ = { 4, 5, t }

32
X
 33
X
X 9

24
2 3
0 9

s
18
14 X 14
 6
2
6 
X 34
X 35
44
30 X
 4 19
11
15 5
5
6
20 16
delmin

t
7 44

132  15
X 51 59 
X X
 Dijkstra's Shortest Path
S = { s, 2, 3, 5, 6, 7 }
Algorithm
PQ = { 4, t }

32
X
 33
X
X 9

24
2 3
0 9

s
18
14 X 14
 6
2
6
X 34
X 35
44 45 X

30 X
 4 19
11
15 5
5
6
20 16

t
7 44

133  15
X 50 51
X 59 
X X
 Dijkstra's Shortest Path
S = { s, 2, 3, 5, 6, 7 }
Algorithm
PQ = { 4, t }

32
X
 33
X
X 9

24
2 3
0 9

s
18
14 X 14
 6
2
6
X 34
X 35
44 45 X

30 X
 4 19
11
15 5 delmin
5
6
20 16

t
7 44

134  15
X 50 51
X 59 
X X
 Dijkstra's Shortest Path
S = { s, 2, 3, 4, 5, 6, 7 }
Algorithm
PQ = { t }

32
X
 33
X
X 9

24
2 3
0 9

s
18
14 X 14
 6
2
6
X 34
X 35
44 45 X

30 X
 4 19
11
15 5
5
6
20 16

t
7 44

135  15
X 50 51
X 59 
X X
 Dijkstra's Shortest Path
S = { s, 2, 3, 4, 5, 6, 7 }
Algorithm
PQ = { t }

32
X
 33
X
X 9

24
2 3
0 9

s
18
14 X 14
 6
2
6
X 34
X 35
44 45 X

30 X
 4 19
11
15 5
5
6
20 16

t
7 44
delmin 50 51
X 59 
X X
136  15
X
 Dijkstra's Shortest Path
S = { s, 2, 3, 4, 5, 6, 7, t }
Algorithm
PQ = { }

32
X
 33
X
X 9

24
2 3
0 9

s
18
14 X 14
 6
2
6
X 34
X 35
44 45 X

30 X
 4 19
11
15 5
5
6
20 16

t
7 44

137  15
X 50 51
X 59 
X X
 Dijkstra's Shortest Path
S = { s, 2, 3, 4, 5, 6, 7, t }
Algorithm
PQ = { }

32
X
 33
X
X 9

24
2 3
0 9

s
18
14 X 14
 6
2
6
X 34
X 35
44 45 X

30 X
 4 19
11
15 5
5
6
20 16

t
7 44

138  15
X 50 51
X 59 
X X