Graph Algorithms

Sumber dari :
dna.cs.byu.edu/CS484/lectures/GraphAlgorithms.ppt
 Definitions and Representation

• An undirected graph G is a pair (V,E), where V is a finite set of

points called vertices and E is a finite set of edges.

• An edge e ∈ E is an unordered pair (u,v), where u,v ∈ V.

• In a directed graph, the edge e is an ordered pair (u,v). An edge

(u,v) is incident from vertex u and is incident to vertex v.

• A path from a vertex v to a vertex u is a sequence <v0,v1,v2,…,vk> of

vertices where v0 = v, vk = u, and (vi, vi+1) ∈ E for I = 0, 1,…, k-1.

• The length of a path is defined as the number of edges in the path.

 Definitions and Representation

a) An undirected graph and (b) a directed graph.

 Definitions and Representation

• An undirected graph is connected if every pair of vertices

is connected by a path.
• A forest is an acyclic graph, and a tree is a connected
acyclic graph.
• A graph that has weights associated with each edge is
called a weighted graph.
 Definitions and Representation

• Graphs can be represented by their adjacency matrix or

an edge (or vertex) list.
• Adjacency matrices have a value ai,j = 1 if nodes i and j
share an edge; 0 otherwise. In case of a weighted graph,
ai,j = wi,j, the weight of the edge.
• The adjacency list representation of a graph G = (V,E)
consists of an array Adj[1..|V|] of lists. Each list Adj[v] is
a list of all vertices adjacent to v.
• For a graph with n nodes, adjacency matrices take Θ(n2)
space and adjacency list takes Θ(|E|) space.
 Definitions and Representation

An undirected graph and its adjacency matrix representation.

An undirected graph and its adjacency list representation.

 Minimum Spanning Tree

• A spanning tree of an undirected graph G is a subgraph

of G that is a tree containing all the vertices of G.
• In a weighted graph, the weight of a subgraph is the sum
of the weights of the edges in the subgraph.
• A minimum spanning tree (MST) for a weighted
undirected graph is a spanning tree with minimum
weight.
 Minimum Spanning Tree

An undirected graph and its minimum spanning tree.

 Minimum Spanning Tree: Prim's
Algorithm
• Prim's algorithm for finding an MST is a greedy
algorithm.
• Start by selecting an arbitrary vertex, include it into the
current MST.
• Grow the current MST by inserting into it the vertex
closest to one of the vertices already in current MST.
Minimum Spanning Tree: Prim's Algorithm

Prim's minimum spanning tree algorithm.

Minimum Spanning Tree: Prim's
Algorithm

Prim's sequential minimum spanning tree algorithm.

 Prim's Algorithm: Parallel Formulation

• The algorithm works in n outer iterations

– it is hard to execute these iterations concurrently.
• The inner loop is relatively easy to parallelize.
• The adjacency matrix is partitioned in a 1-D block
fashion, with distance vector d partitioned accordingly.
• In each step,
– a processor selects the locally closest node,
– followed by a global reduction to select globally closest node.
• This node is inserted into MST,
– broadcast to all processors.
• Each processor updates its part of the d vector locally.
Prim's Algorithm: Parallel Formulation

The partitioning of the distance array d and the adjacency matrix A

among p processes.
 Single-Source Shortest Paths

• For a weighted graph G = (V,E,w), the single-source

shortest paths problem is to find the shortest paths from
a vertex v ∈ V to all other vertices in V.
• Dijkstra's algorithm is similar to Prim's algorithm.
– maintains a set of nodes for which the shortest paths are known.
– grow this set based on the node closest to source using one of
the nodes in the current shortest path set.
Single-Source Shortest Paths: Dijkstra's
Algorithm

Dijkstra's sequential single-source shortest paths algorithm.

 Dijkstra's Algorithm: Parallel
Formulation
• Very similar to the parallel formulation of Prim's
algorithm for minimum spanning trees.
• The weighted adjacency matrix is partitioned using the 1-
D block mapping.
• Each process selects, locally, the node closest to the
source, followed by a global reduction to select next
node.
• The node is broadcast to all processors and the l-vector
updated.
• The parallel performance of Dijkstra's algorithm is
identical to that of Prim's algorithm.
 All-Pairs Shortest Paths

• Given a weighted graph G(V,E,w), the all-pairs shortest

paths problem is to find the shortest paths between all
pairs of vertices vi, vj ∈ V.
• A number of algorithms are known for solving this
problem.
 All-Pairs Shortest Paths: Matrix-
Multiplication Based Algorithm
• Consider the multiplication of the weighted adjacency
matrix with itself - except,
– replace the multiplication operation in matrix multiplication by
addition, and the addition operation by minimization.
• Notice that the product of weighted adjacency matrix
with itself returns a matrix that contains shortest paths of
length 2 between any pair of nodes.
• It follows from this argument that An contains all shortest
paths.
Matrix-Multiplication Based Algorithm
 Matrix-Multiplication Based Algorithm

• An is computed by doubling powers - i.e., as A, A2, A4,

A8, and so on.
• We need log n matrix multiplications, each taking time
O(n3).
• The serial complexity of this procedure is O(n3log n).
• This algorithm is not optimal, since the best known
algorithms have complexity O(n3).
 Matrix-Multiplication Based Algorithm:
Parallel Formulation
• Each of the log n matrix multiplications can be performed
in parallel.
• We can use n3/log n processors to compute each matrix-
matrix product in time log n.
• The entire process takes O(log2n) time.
 Dijkstra's Algorithm

• Execute n instances of the single-source shortest path

problem, one for each of the n source vertices.
• Complexity is O(n3).

• Two parallelization strategies

– execute each of the n shortest path problems on a different
processor (source partitioned), or
– use a parallel formulation of the shortest path problem to
increase concurrency (source parallel).
Dijkstra's Algorithm: Source Partitioned

• Use n processors,
– each processor Pi finds the shortest paths from vertex vi to all
other vertices by executing Dijkstra's sequential single-source
shortest paths algorithm.
• Requires no interprocess communication
– provided that the adjacency matrix is replicated at all processes.
• The parallel run time is: Θ(n2).

• While the algorithm is cost optimal, it can only use n

processors.
 Dijkstra's Algorithm: Source Parallel

• In this case, each of the shortest path problems is further

executed in parallel. We can therefore use up to n2
processors.
• Given p processors (p > n), each single source shortest
path problem is executed by p/n processors.
• Using previous results, this takes time:
 Floyd's Algorithm

• For any pair of vertices vi, vj ∈ V, consider all paths from

vi to vj whose intermediate vertices belong to the set
{v1,v2,…,vk}.
• Let pi(,kj) (of weight di(,kj)) be the minimum-weight path
among them.
• If vertex vk is not in the shortest path from vi to vj, then
pi(,kj) is the same as pi(,kj-1).
• If f vk is in pi(,kj), then we can break pi(,kj) into two paths -
one from vi to vk and one from vk to vj . Each of these
paths uses vertices from {v1,v2,…,vk-1}.
 Floyd's Algorithm

From our observations, the following recurrence relation

follows:

This equation must be computed for each pair of nodes

and for k = 1, n. The serial complexity is O(n3).
 Floyd's Algorithm

Floyd's all-pairs shortest paths algorithm.

This program computes the all-pairs shortest paths of the
graph G = (V,E) with adjacency matrix A.
 Floyd's Algorithm: Parallel Formulation
Using 2-D Block Mapping
• The n x n distance matrix D(k) is divided into p blocks of
size (n / √p) x (n / √p).
• Each processor updates its part of the matrix during
each iteration.
• To compute dl(,kr-1) processor Pi,j must get dl(,kk-1) and
dk(,kr-1).
• In general, during the kth iteration, each of the √p
processes containing part of the kth row send it to the √p
- 1 processes in the same column.
• Similarly, each of the √p processes containing part of the
kth column sends it to the √p - 1 processes in the same
row.
 Floyd's Algorithm: Parallel Formulation
Using 2-D Block Mapping

(a) Matrix D(k) distributed by 2-D block mapping into √p x √p subblocks,

and (b) the subblock of D(k) assigned to process Pi,j.
Floyd's Algorithm: Parallel Formulation
Using 2-D Block Mapping

(a) Communication patterns used in the 2-D block mapping. When computing di(,kj),
information must be sent to the highlighted process from two other processes along
the same row and column. (b) The row and column of √p processes that contain the
kth row and column send them along process columns and rows.
Floyd's Algorithm: Parallel Formulation
Using 2-D Block Mapping

Floyd's parallel formulation using the 2-D block mapping.

P*,j denotes all the processes in the jth column, and Pi,* denotes all the
processes in the ith row. The matrix D(0) is the adjacency matrix.
 Floyd's Algorithm: Parallel Formulation
Using 2-D Block Mapping
• During each iteration of the algorithm, the kth row and kth
column of processors perform a one-to-all broadcast
along their rows/columns.
• The size of this broadcast is n/√p elements, taking time
Θ((n log p)/ √p).
• The synchronization step takes time Θ(log p).
• The computation time is Θ(n2/p).
• The parallel run time of the 2-D block mapping
formulation of Floyd's algorithm is
 Floyd's Algorithm: Speeding Things Up
by Pipelining
• The synchronization step in parallel Floyd's algorithm can be
removed without affecting the correctness of the algorithm.
• A process starts working on the kth iteration as soon as it has
computed the (k-1)th iteration and has the relevant parts of the D(k-1)
matrix.
• The overall parallel run time is

• The pipelined formulation of Floyd's algorithm uses up to O(n2)

processes efficiently.
 All-pairs Shortest Path: Comparison

• The performance and scalability of the all-pairs shortest

paths algorithms on various architectures with bisection
bandwidth. Similar run times apply to all cube
architectures, provided that processes are properly
mapped to the underlying processors.
 Transitive Closure

• If G = (V,E) is a graph, then the transitive closure of G is

defined as the graph G* = (V,E*), where E* = {(vi,vj) |
there is a path from vi to vj in G}
• The connectivity matrix of G is a matrix A* = (ai*,j) such
that ai*,j = 1 if there is a path from vi to vj or i = j, and ai*,j =
∞ otherwise.
• To compute A* we assign a weight of 1 to each edge of
E and use any of the all-pairs shortest paths algorithms
on this weighted graph.
 Algorithms for Sparse Graphs

• A graph G = (V,E) is sparse if |E| is much smaller than

|V|2.

Examples of sparse graphs: (a) a linear graph, in which each vertex has two incident
edges; (b) a grid graph, in which each vertex has four incident vertices; and (c) a
random sparse graph.
 Algorithms for Sparse Graphs

• Dense algorithms can be improved significantly if we

make use of the sparseness.
– For example, the run time of Prim's minimum spanning tree
algorithm can be reduced from Θ(n2) to Θ(|E| log n).
• Sparse algorithms use an adjacency list instead of an
adjacency matrix.
• Partitioning adjacency lists is more difficult for sparse
graphs
– do we balance number of vertices or edges?
• Parallel algorithms typically make use of graph structure
or degree information for performance.
 Algorithms for Sparse Graphs

A street map (a) can be represented by a graph (b). In the graph shown
in (b), each street intersection is a vertex and each edge is a street
segment. The vertices of (b) are the intersections of (a) marked by
dots.
 Single-Source Shortest Paths

• Dijkstra's algorithm, modified to handle sparse graphs is

called Johnson's algorithm.
• The modification accounts for the fact that the
minimization step in Dijkstra's algorithm needs to be
performed only for those nodes adjacent to the
previously selected nodes.
• Johnson's algorithm uses a priority queue Q to store the
value l[v] for each vertex v ∈ (V – VT).
Single-Source Shortest Paths: Johnson's
Algorithm

Johnson's sequential single-source shortest paths algorithm.

 Single-Source Shortest Paths: Parallel
Johnson's Algorithm
• Maintaining strict order of Johnson's algorithm
sequentializes the algorithm.
• We need to allow exploration of multiple nodes
concurrently.
– Simultaneously extract p nodes from the priority queue, updating
the neighbors' cost, and augmenting the shortest path.
• If an error is made, it can be discovered (as a shorter
path) and the node can be reinserted with this shorter
path.
 Single-Source Shortest Paths: Parallel
Johnson's Algorithm

An example of the modified Johnson's algorithm for processing unsafe vertices

concurrently.
 Single-Source Shortest Paths: Parallel
Johnson's Algorithm
• Even if we can extract and process multiple nodes from
the queue, the queue itself is a major bottleneck.
• Use multiple queues, one for each processor.
– Each processor builds its priority queue only using its own
vertices.
• When process Pi extracts the vertex u ∈ Vi,
– Send a message to processes that store vertices adjacent to u.
• Process Pj, upon receiving this message, sets the value
of l[v] stored in its priority queue to min{l[v],l[u] + w(u,v)}.
 Single-Source Shortest Paths: Parallel
Johnson's Algorithm
• If a shorter path has been discovered to node v, it is
reinserted back into the local priority queue.
• The algorithm terminates only when all the queues
become empty.
• A number of node paritioning schemes can be used to
exploit graph structure for performance.