Transcript CE221_week_12

CE 221
Data Structures and Algorithms
Chapter 9 : Graphs Part I
(Topological Sort & Shortest Path
Algorithms)
Text: Read Weiss, §9.1 – 9.3
Izmir University of Economics
1
Definitions - I
• A graph G=(V, E) consists of a set of vertices,
V, and a set of edges, E.
• Each edge is a pair (v, w), where v, w є V.
• If the pair is ordered then G is directed
(digraph).
• Vertex w is adjacent to v iff (v, w) є E.
• In an undirected graph with edge (v, w), w is
adjacent to v and v is adjacent to w.
• Sometimes and edge has a third component,
weight or cost.
Izmir University of Economics
2
Definitions - II
• A path in a graph is w1, w2,...,wN such that
(wi, wi+1) є E for 1≤i<N. The length of such
a path is the number of edges on the path.
If a path from a vertex to itself contains no
edges, then the path length is zero. If G
contains an edge (v, v), then the path v, v
is called a loop.
• A simple path is a path such that all
vertices are distinct, except that the first
and the last could be the same.
Izmir University of Economics
3
Definitions - III
• A cycle in a directed graph is a path of length at
least 1 such that w1=wN. This cycle is simple if the
path is simple. For undirected graphs, the edges are
required to be distinct (Why?).
• A directed graph is acyclic if it has no cycles (DAG).
• An undirected graph is connected if there is a path
from every vertex to every other vertex. A directed
graph with this property is called strongly
connected. If directed graph is not, but underlying
undirected graph is, it is weakly connected. A
complete graph is a graph in which there is an
edge between every pair of vertices.
Izmir University of Economics
4
Representation of Graphs - I
• One simple way is to use a twodimensional array (adjacency matrix
representation). If vertices are numbered
starting at 1, A[u][v]=true if (u, v) є E.
Space requirement is Θ(|V|2).
• If the graph is not dense (sparse),
adjacency lists may be used. The space
requirement is O(|E|+|V|).
Izmir University of Economics
5
Representation of Graphs - II
Izmir University of Economics
6
Topological Sort - I
•A topological sort is an ordering of vertices
in a DAG, such that if there is path from vi to
vj, then vj appears after vi in the ordering.
•A simple algorithm to find a topological
ordering is first to find any vertex with no
incoming edges. We can then print this vertex,
and remove it, along with its edges. Then apply
the same strategy to the rest of the graph. To
formalize this, define the indegree of a vertex
v as the number of edges (u, v).
Izmir University of Economics
7
Topological Sort – Initial Attempt
• running time of
the algorithm is
O(|V|2).
Izmir University of Economics
8
Topological Sort – A Better Algorithm
• We can remove the inefficiency by
keeping all the unassigned vertices
of indegree 0 in a special data
structure (queue or stack). When a
new vertex with degree zero is
needed, it is returned by removing
one from the queue, and when the
indegrees of adjacent vertices are
decremented, they are inserted into
the queue if the indegree falls to
zero. The running time is O(|E|+|V|)
Izmir University of Economics
9
Homework Assignments
• 9.1, 9.2, 9.3, 9.4, 9.38
• You are requested to study and solve the
exercises. Note that these are for you to
practice only. You are not to deliver the
results to me.
Izmir University of Economics
10
Shortest-Path Algorithms
• The input is a weighted graph: associated
with each edge (vi, vj) is a cost ci,j. The
cost of a path v1v2...vN is ∑ci,i+1 for i in
[1..N-1]. This is weighted path length, the
unweighted path length on the other
hand is merely the number of edges on
the path, namely, N-1.
• Single-source Shortest-Path Problem:
Given as input a weighted graph G=(V, E),
and a distinguished vertex, s, find the
shortest weighted path from s to every
other vertex in G.
Izmir University of Economics
11
Negative Cost Cycles
• In the graph to the left, the shortest path from v1 to v6 has a
cost of 6 and the path itself is v1v4v7v6. The shortest
unweighted path has 2 edges.
• In the graph to the right, we have a negative cost. The path
from v5 to v4 has cost 1, but a shorter path exists by following
the loop v5v4v2v5v4 which has cost -5. This path is still not the
shortest, because we could stay in the loop arbitrarily long.
Izmir University of Economics
12
Shortest Path Length: Problems
We will examine 4 algorithms to solve four versions of
the problem
1. Unweighted shortest path  O(|E|+|V|)
2. Weighted shortest path without negative edges 
O(|E|log|V|) using queues
3. Weighted shortest path with negative edges
O(|E| . |V|)

4. Weighted shortest path of acyclic graphs  linear
time
Izmir University of Economics
13
Unweighted Shortest Paths
• Using some vertex, s, which is an input
parameter, find the shortest path from s to all
other vertices in an unweighted graph. Assume
s=v3.
Izmir University of Economics
14
Unweighted Shortest Paths
• Algorithm: find vertices that are at
distance 1, 2, ... N-1 by processing
vertices in layers (breadth-first search)
Izmir University of Economics
15
Unweighted Shortest Paths
Izmir University of Economics
16
Unweighted Shortest Paths
• Complexity O(|V|2)
Izmir University of Economics
17
Unweighted Shortest Paths - Improvement
• At any point in time there
are only two types of
unknown vertices that
have dv≠∞. Some have
dv = currDist and the rest
have dv = currDist +1.
• We can make use of a
queue data structure.
• O(|E|+|V|)
Izmir University of Economics
18
Weighted Shortest Path
Dijkstra’s Algorithm
• With weighted shortest path,distance dv is
tentative. It turns out to be the shortest path
length from s to v using only known vertices as
intermediates.
• Greedy algorithm: proceeds in stages doing the
best at each stage. Dijkstra’s algorithm selects a
vertex v with smallest dv among all unknown
vertices and declares it known. Remainder of the
stage consists of updating the values dw for all
edges (v, w).
Izmir University of Economics
19
Dijkstra’s Algorithm - Example
►
►
►
Izmir University of Economics
20
Dijkstra’s Algorithm - Example
►
►
►
►
• A proof by contradiction will show that this
algorithm always works as long as no
edge has a negative cost.
Izmir University of Economics
21
Dijkstra’s Algorithm - Pseudocode
• If the vertices are
sequentially scanned to
find minimum dv, each
phase will take O(|V|) to
find the minimum, thus
O(|V|2) over the course
of the algorithm.
• The time for updates is
constant and at most
one update per edge for
a total of O(|E|).
• Therefore the total time
spent is O(|V|2+|E|).
• If the graph is dense,
OPTIMAL.
Izmir University of Economics
22
Dijkstra’s Algorithm-What if the
graph is sparse?
• If the graph is sparse |E|=θ(|V|), algorithm is too
slow. The distances of vertices need to be kept
in a priority queue.
• Selection of vertex with minimum distance via
deleteMin, and updates via decreaseKey
operation. Hence; O(|E|log|V|+|V|log|V|)
• find operations are not supported, so you need
to be able to maintain locations of di in the heap
and update them as they change.
• Alternative: insert w and dw with every update.
Izmir University of Economics
23
Graphs with negative edge
costs
• Dijkstra’s algorithm does not work with
negative edge costs. Once a vertex u is
known, it is possible that from some other
unknown vertex v, there is a path back to
u that is very negative.
• Algorithm: A combination of weighted and
unweighted algorithms. Forget about the
concept of known vertices.
Izmir University of Economics
24
Graphs with negative edge costs - I
• O(|E|*|V|). Each vertex
can dequeue at most
O(|V|) times. (Why?
Algorithm computes
shortest paths with at
most 0, 1, ..., |V|-1 edges
in this order). Hence, the
result!
• If negative cost cycles,
then each vertex should
be checked to have been
dequeued at most |V|
times.
Izmir University of Economics
25
Acyclic Graphs
• If the graph is known to be acyclic, the
order in which vertices are declared
known, can be set to be the topological
order.
• Running time = O(|V|+|E|)
• This selection rule works because when a
vertex is selected, its distance can no
longer be lowered, since by topological
ordering rule it has no incoming edges
emanating from unknown nodes.
Izmir University of Economics
26
Homework Assignments
• 9.5, 9.7, 9.10, 9.40, 9.42, 9.44, 9.46, 9.47,
9.52
• You are requested to study and solve the
exercises. Note that these are for you to
practice only. You are not to deliver the
results to me.
Izmir University of Economics
27