Design & Analysis of Algorithms

(KCS 503)
UNIT-3 & 4
Graph Algorithms (Greedy Algorithms)

From:
Asif Khan
Department of CSE
GNIOT, Greater Noida

Reference:
Thomas H. Corman et al.
The MIT Press
 Minimum Spanning Tree
Electronic circuit designs often need to make the
pins of several components electrically equivalent
by wiring them together. To interconnect a set of n
pins, we can use an arrangement of n-1 wires, each
connecting two pins.
Of all such arrangements, the one that uses the
least amount of wire is usually the most desirable.
We can model this wiring problem with a
connected, undirected graph G = (V, E), where V is
the set of pins, E is the set of possible
interconnections between pairs of pins, and for
 Minimum Spanning Tree
each edge (u,v) ϵ E , we have a weight w(u,v)
specifying the cost (amount of wire needed) to
connect u and v. We then wish to find an acyclic
subset T of E that connects all of the vertices and
whose total weight

is minimized. Since T is acyclic and connects all of

the vertices, it must form a tree, which we call a
spanning tree since it “spans” the graph G. We call
the problem of determining the tree T the
minimum-spanning-tree
 Minimum Spanning Tree
2 2
3
3 6 3 6 3 6
4
5 5
wt=11 wt=14
2 2
3 3
3 3 6
4
5
wt=9 wt=10 wt=12
 Kruskal’s algorithm
Kruskal’s algorithm finds a safe edge to add to the
growing forest by finding, of all the edges that
connect any two trees in the forest, an edge (u,v)
of least weight.
1. A = Φ
2. Arrange all edges E of graph G in non
decreasing order of their weight.
3. for each edge (u,v) of E taken in non decreasing
order of their weight.
4. if solution is feasible (there is no cycle)
5. A= A U {(u,v)}
6. return A
MST using Kruskal’s algorithm-An Example

a 2 b 4 c 2
a b c
3 2 2
3
3 6 6 3
4 5
d e f d e f
5 7

a 2 b 4 c a 2 b c
2 2
3 3
5
4 4
d e f d e f

Total weight of MST=2+2+3+4+5=16

 Kruskal’s algorithm
Our implementation of Kruskal’s algorithm uses a
disjoint-set data structure to maintain several
disjoint sets of elements. Each set contains the
vertices in one tree of the current forest. Kruskal’s
algorithm uses following three operations:
MAKE-SET(u) This operation creates a new set
with a single value {u}. U is also the
representative of this set.
FIND-SET(u) This operation returns a
representative element from the set that contains u.
Thus, we can determine whether two vertices u
 Kruskal’s algorithm
and v belong to the same tree by testing whether
FIND-SET(u) equals FIND-SET(v).
UNION(u,v) To combine trees, Kruskal’s
algorithm calls the UNION procedure. This
function unites the two sets to whom the elements
u and v belongs to.
Kruskal’s algorithm
 Kruskal’s algorithm
A=Φ 2 4
a b c
{a}, {b}, {c}, {d}, {e}, {f} 3 2
{a,b}, {c}, {d}, {e}, {f} 3 6 6
{a,b}, {c,e}, {d}, {f} 4 5
d e f
5 7
{a,b,d}, {c,e}, {f}
{a,b,d,c,e}, {f} a 2 b 4 c
2
{a,b,d,c,e,f}
3
5
d e f
 Kruskal’s algorithm
Example 2

2
Kruskal’s algorithm

2
Kruskal’s algorithm

2
 Prim’s Algorithm
Prim’s algorithm operates much like Dijkstra’s
algorithm for finding shortest paths in a graph,
which we shall see in next Section.
Prim’s algorithm has the property that the edges in
the set A always form a single tree.
The tree starts from an arbitrary root vertex r and
grows until the tree spans all the vertices in V.
Each step adds to the tree A a light edge that
connects A to an isolated vertex—one on which no
edge of A is incident.
 Prim’s Algorithm
This rule adds only edges that are safe for A;
therefore, when the algorithm terminates, the
edges in A form a minimum spanning tree. This
strategy qualifies as greedy since at each step it
adds to the tree an edge that contributes the
minimum amount possible to the tree’s weight.
Example of Prim’s Algorithm
Example of Prim’s Algorithm
Example of Prim’s Algorithm
Example of Prim’s Algorithm
 Single-Source Shortest Paths
Negative-weight edges: Some instances of the
single-source shortest-paths problem may include
edges whose weights are negative. If the graph
G=(V, E) contains no negative weight cycles
reachable from the source s, then for all v ϵ V , the
shortest-path weight δ(s, v) remains well defined,
even if it has a negative value.
If the graph contains a negative-weight cycle
reachable from s, however, shortest-path weights
are not well defined. No path from s to a vertex on
the cycle can be a shortest.
 Single-Source Shortest Paths
No path from s to a vertex on the cycle can be a
shortest- we can always find a path with lower
weight by following the proposed “shortest” path
and then traversing the negative-weight cycle. If
there is a negative weight cycle on some path from
s to v, we define δ(s, v) = -∞.
 Single-Source Shortest Paths
Following two functions will be used in both the
algorithms of single source shortest paths
 Bellman-Ford Algorithm
The Bellman-Ford algorithm solves the single-
source shortest-paths problem in the general case in
which edge weights may be negative.
Given a weighted, directed graph G=(V, E) with
source s and weight function w, the Bellman-Ford
algorithm returns a boolean value indicating whether
or not there is a negative-weight cycle that is
reachable from the source.
If there is such a cycle, the algorithm indicates that
no solution exists. If there is no such cycle, the
algorithm produces the shortest paths and their
weights.
Bellman-Ford Algorithm
Example of Bellman-Ford Algorithm
Example of Bellman-Ford Algorithm
 Dijkstra’s Algorithm
Dijkstra’s algorithm solves the single-source
shortest-paths problem on a weighted, directed
graph G=(V, E) for the case in which all edge
weights are nonnegative.
In this algorithm, therefore, we assume that
w(u,v)≥0 for each edge (u, v) ϵ E.
The running time of Dijkstra’s algorithm is lower
than that of the Bellman-Ford algorithm.
Dijkstra’s algorithm maintains a set S of vertices
whose final shortest-path weights from the source s
have already been determined.
 Dijkstra’s Algorithm
The algorithm repeatedly selects the vertex u ϵ V - S with
the minimum shortest-path estimate, adds u to S, and
relaxes all edges leaving u. In the following
implementation, we use a min-priority queue Q of
vertices, keyed by their d values.
Example-Dijkstra’s Algorithm
Example-Dijkstra’s Algorithm
 Example-Dijkstra’s Algorithm
We can solve the problem by using
tabulation method also.

s t x y z
0 ∞ ∞ ∞ ∞
s 0 10 ∞ 5 ∞
y 0 8 14 5 7
z 0 8 13 5 7
t 0 8 9 5 7
x 0 8 9 5 7
 Example-Dijkstra’s Algorithm

s t x y z
0 ∞ ∞ ∞ ∞
s 0 10 ∞ 5 ∞
y 0 8 14 5 7
z 0 8 13 5 7
t 0 8 9 5 7
x 0 8 9 5 7
THANK YOU