Lecture 20: Topo-Sort and Dijkstras Greedy Idea
! Items on Todays Lunch Menu: " Topological Sort (ver. 1 & 2): Gunning for linear time " Finding Shortest Paths # Breadth-First Search # Dijkstras Method: Greed is good!
! Covered in Chapter 9 in the textbook
R. Rao, CSE 326
Some slides based on: CSE 326 by S. Wolfman, 2000
Graph Algorithm #1: Topological Sort
143 322 321 326 370 341
142
Problem: Find an order in which all these courses can be taken. Example: 142 143 378 370 321 341 322 326 421 401
R. Rao, CSE 326
378 421 401
Topological Sort Definition
Topological sorting problem: given digraph G = (V, E) , find a linear ordering of vertices such that: for all edges (v, w) in E, v precedes w in the ordering
B C A F D E
3
R. Rao, CSE 326
Topological Sort
Topological sorting problem: given digraph G = (V, E) , find a linear ordering of vertices such that: for any edge (v, w) in E, v precedes w in the ordering
B C A F D E A
R. Rao, CSE 326
Any linear ordering in which all the arrows go to the right is a valid solution
D
4
Topological Sort
Topological sorting problem: given digraph G = (V, E) , find a linear ordering of vertices such that: for any edge (v, w) in E, v precedes w in the ordering
B C A F D E A
R. Rao, CSE 326
Not a valid topological sort!
D
5
Topological Sort Algorithm
Step 1: Identify vertices that have no incoming edge
The in-degree of these vertices is zero B A C F D E
R. Rao, CSE 326
Topological Sort Algorithm
Step 1: Identify vertices that have no incoming edge
If no such edges, graph has cycles (cyclic graph) B A C
Example of a cyclic graph: No vertex of in-degree 0
R. Rao, CSE 326
Topological Sort Algorithm
Step 1: Identify vertices that have no incoming edges
Select one such vertex Select B A C F D E
R. Rao, CSE 326
Topological Sort Algorithm
Step 2: Delete this vertex of in-degree 0 and all its outgoing edges from the graph. Place it in the output.
B C F D E A
R. Rao, CSE 326
Topological Sort Algorithm
Repeat Steps 1 and Step 2 until graph is empty
Select B C F D E A
R. Rao, CSE 326
10
Topological Sort Algorithm
Repeat Steps 1 and Step 2 until graph is empty
Select F A B
R. Rao, CSE 326
11
Topological Sort Algorithm
Repeat Steps 1 and Step 2 until graph is empty
Select C A D E B F
R. Rao, CSE 326
12
Topological Sort Algorithm
Repeat Steps 1 and Step 2 until graph is empty
Final Result:
A B F C D E
R. Rao, CSE 326
13
Summary of Topo-Sort Algorithm #1
Store each vertexs InDegree (# of incoming A edges) in an array 2. While there are vertices remaining: " Find a vertex with 0 In-Degree zero and output it 1 " Reduce In-Degree of 1 all vertices adjacent to it by 1 2 " Mark this vertex (InDegree = -1) 2 In-Degree R. Rao, CSE 326 array 0
1.
C E B C D E Adjacency list E D
D A B C D E F
14
Topological Sort Algorithm #1: Analysis
For input graph G = (V,E), Run Time = ?
Break down into total time required to: Initialize In-Degree array: O(|E|) Find vertex with in-degree 0: |V| vertices, each takes O(|V|) to search In-Degree array. Total time = O(|V|2) Reduce In-Degree of all vertices adjacent to a vertex: O(|E|) Output and mark vertex: O(|V|) Total time = O(|V|2 + |E|) Quadratic time!
R. Rao, CSE 326 15
Can we do better than quadratic time?
Problem: Need a faster way to find vertices with in-degree 0 instead of searching through entire in-degree array
R. Rao, CSE 326
16
Topological Sort (Take 2)
Key idea: Initialize and maintain a queue (or stack) of vertices with In-Degree 0
Queue A F 0 A B A D E C 1 B F 1 C 2 D 2 E In-Degree array 0 F B C D E Adjacency list E D
R. Rao, CSE 326
17
Topological Sort (Take 2)
After each vertex is output, when updating In-Degree array, enqueue any vertex whose In-Degree has become zero Queue
dequeue enqueue
B 0 A 0 B 1 C F 1 D B C D E Adjacency list E D
Output A B A D
R. Rao, CSE 326
C E
2 E In-Degree array 0 F
18
Topological Sort Algorithm #2
1. 2. 3.
Store each vertexs In-Degree in an array Initialize a queue with all in-degree zero vertices While there are vertices remaining in the queue: " Dequeue and output a vertex " Reduce In-Degree of all vertices adjacent to it by 1 " Enqueue any of these vertices whose In-Degree became zero B A D E C F Sort this digraph!
19
R. Rao, CSE 326
Topological Sort Algorithm #2: Analysis
For input graph G = (V,E), Run Time = ?
Break down into total time to: Initialize In-Degree array: O(|E|) Initialize Queue with In-Degree 0 vertices: O(|V|) Dequeue and output vertex: |V| vertices, each takes only O(1) to dequeue and output. Total time = O(|V|) Reduce In-Degree of all vertices adjacent to a vertex and Enqueue any In-Degree 0 vertices: O(|E|) Total time = O(|V| + |E|) Linear running time!
20
R. Rao, CSE 326
Paths
! Recall definition of a path in a tree same for graphs ! A path is a list of vertices {v1, v2, , vn} such that
(vi, vi+1) is in E for all 0 ! i < n.
Chicago Seattle Salt Lake City Example of a path: p = {Seattle, Salt Lake City, Chicago, Dallas, San Francisco, Seattle}
21
San Francisco Dallas
R. Rao, CSE 326
Simple Paths and Cycles
! A simple path repeats no vertices (except the 1st can be the
last):
" p = {Seattle, Salt Lake City, San Francisco, Dallas} " p = {Seattle, Salt Lake City, Dallas, San Francisco, Seattle}
! A cycle is a path that starts and ends at the same node:
" p = {Seattle, Salt Lake City, Dallas, San Francisco, Seattle}
! A simple cycle is a cycle that repeats no vertices except that
the first vertex is also the last
! A directed graph with no cycles is called a DAG (directed
acyclic graph) E.g. All trees are DAGs
" A graph with cycles is often a drag
R. Rao, CSE 326
22
Path Length and Cost
! Path length: the number of edges in the path ! Path cost: the sum of the costs of each edge
" Note: Path length = unweighted path cost (edge weight = 1)
3.5
Chicago
2
Seattle
2 2
Salt Lake City
2.5 2.5 3 2.5
length(p) = 5 San Francisco
R. Rao, CSE 326
cost(p) = 11.5 Dallas
23
Single Source, Shortest Path Problems
! Given a graph G = (V, E) and a source vertex s in V, find
the minimum cost paths from s to every vertex in V
! Many variations:
" unweighted vs. weighted " cyclic vs. acyclic " positive weights only vs. negative weights allowed " multiple weight types to optimize " Etc.
! We will look at only a couple of these
" See text for the others
R. Rao, CSE 326 24
Why study shortest path problems?
! Plenty of applications ! Traveling on a starving student budget: What is the
cheapest multi-stop airline schedule from Seattle to city X?
! Optimizing routing of packets on the internet:
" Vertices = routers, edges = network links with different delays " What is the routing path with smallest total delay?
! Hassle-free commuting: Finding what highways and roads to
take to minimize total delay due to traffic
! Finding the fastest way to get to coffee vendors on campus
from your classrooms
R. Rao, CSE 326 25
Unweighted Shortest Paths Problem
Problem: Given a source vertex s in an unweighted graph G = (V,E), find the shortest path from s to all vertices in G
A B F G E H
C Source D
Find the shortest path from C to: A
R. Rao, CSE 326
H
26
Solution based on Breadth-First Search
! Basic Idea: Starting at node s, find vertices that can be
reached using 0, 1, 2, 3, , N-1 edges (works even for cyclic graphs!)
A B F G C D H
On-board example: Find the shortest path from C to: A
R. Rao, CSE 326
E B C D E F G H
27
Breadth-First Search (BFS) Algorithm
! Uses a queue to store vertices that need to be expanded ! Pseudocode (source vertex is s): 1. Dist[s] = 0 2. Enqueue(s) 3. While queue is not empty 1. X = dequeue 2. For each vertex Y adjacent to X and not previously visited (Prev allows $ Dist[Y] = Dist[X] + 1 paths to be $ Prev[Y] = X $ Enqueue Y reconstructed) ! Running time (same as topological sort) = O(|V| + |E|) (why?)
R. Rao, CSE 326 28
That was easy but what if edges have weights?
Does BFS still work for finding minimum cost paths?
2
A
1 3 9 1
8 3
Can you find a counterexample (a path) for this graph to show BFS wont work?
R. Rao, CSE 326
29
What if edges have weights?
! BFS does not work anymore minimum cost path may have
additional hops Shortest path from C to A: BFS: C A (cost = 9) Minimum Cost Path = C E D A (cost = 8)
2
A
1 3 9 8 1
D
3
R. Rao, CSE 326
30
Dijkstra to the rescue
! Legendary figure in computer science ! Some rumors collected from previous classes ! Rumor #1: Supported teaching introductory computer
E. W. Dijkstra (1930-2002)
courses without computers (pencil and paper programming)
! Rumor #2: Supposedly wouldnt read his e-mail; so, his
staff had to print out his e-mails and put them in his mailbox
R. Rao, CSE 326
31
An Aside: Dijsktra on GOTOs
For a number of years I have been familiar with the observation that the quality of programmers is a decreasing function of the density of go to statements in the programs they produce.
Opening sentence of: Go To Statement Considered Harmful by Edsger W. Dijkstra, Letter to the Editor, Communications of the ACM, Vol. 11, No. 3, March 1968, pp. 147-148.
R. Rao, CSE 326 32
Dijkstras Algorithm for Weighted Shortest Path
! Classic algorithm for solving shortest path in weighted
graphs (without negative weights)
! Example of a greedy algorithm
" Irrevocably makes decisions without considering future consequences " Sound familiar? Not necessarily the best life strategy but works in some cases (e.g. Huffman encoding)
R. Rao, CSE 326
33
Dijkstras Algorithm for Weighted Shortest Path
! Basic Idea:
" Similar to BFS # Each vertex stores a cost for path from source # Vertex to be expanded is the one with least path cost seen so far $ Greedy choice always select current best vertex $ Update costs of all neighbors of selected vertex " But unlike BFS, a vertex already visited may be updated if a better path to it is found
R. Rao, CSE 326
34
Pseudocode for Dijkstras Algorithm
1. 2. 3.
Initialize the cost of each node to " Initialize the cost of the source to 0
2
B
1
1 While there are unknown nodes left in the 9 graph 3 1. Select the unknown node N with the C 8 2 lowest cost (greedy choice) D 3 2. Mark N as known E 3. For each node X adjacent to N If (Ns cost + cost of (N, X)) < Xs cost (Prev allows Xs cost = Ns cost + cost of (N, X) paths to be Prev[X] = N //store preceding node reconstructed)
35
R. Rao, CSE 326
Dijkstras Algorithm (greed in action)
vertex A B C D E known No No Yes No No cost " " 0 " " 2 Prev vertex known A B C D E cost Prev
Initial
A
3 9 8 1
Final
B
1
C
3
D
R. Rao, CSE 326
E
36
Dijkstras Algorithm (greed in action)
vertex A B C D E known No No Yes No No cost " " 0 " " Prev 2 vertex A B C D E known Yes Yes Yes Yes Yes cost 8 10 0 5 2 Prev D A E C
Initial
A
3 9 8 1
Final
B
1
C
3
D
R. Rao, CSE 326
E
37
Questions for Next Time: Does Dijkstras method always work? How fast does it run? Where else in life can I be greedy? To Do: Start Homework Assignment #4 (Dont wait until the last few days!!!) Continue reading and enjoying chapter 9
R. Rao, CSE 326 38
