CSE 326: Data StructuresGraph AlgorithmsGraph SearchLecture 231Problem: Large Graphs It is expensive to find optimal paths in large graphs, using BFS or Dijkstra’s algorithm (for weighted graphs) How can we search large graphs efficiently by using “commonsense” about which direction looks most promising?2Example352ndSt51stSt50thSt10thAve9thAve8thAve7thAve6thAve5thAve4thAve3rdAve2ndAveSG53ndStPlan a route from 9th& 50thto 3rd& 51stExample452ndSt51stSt50thSt10thAve9thAve8thAve7thAve6thAve5thAve4thAve3rdAve2ndAveSG53ndStPlan a route from 9th& 50thto 3rd& 51stBest‐First Search• The Manhattan distance (Δ x+ Δ y) is an estimate of the distance to the goal– It is a search heuristic Best‐First Search– Order nodes in priority to minimize estimated distance to the goal Compare: BFS / Dijkstra– Order nodes in priority to minimize distance from the start5Best‐First Search• Best_First_Search( Start, Goal_test)• insert(Start, h(Start), heap);• repeat• if (empty(heap)) then return fail;• Node := deleteMin(heap);• if (Goal_test(Node)) then return Node;• for each Child of node do• if (Child not already visited) then• insert(Child, h(Child),heap);• end• Mark Node as visited;• end6Open – Heap (priority queue)Criteria – Smallest key (highest priority)h(n) – heuristic estimate of distance from n to closest goalObstacles• Best‐FS eventually will expand vertex to get back on the right track752ndSt51stSt50thSt10thAve9thAve8thAve7thAve6thAve5thAve4thAve3rdAve2ndAveSGNon‐Optimality of Best‐First852ndSt51stSt50thSt10thAve9thAve8thAve7thAve6thAve5thAve4thAve3rdAve2ndAveS G53ndStPath found by Best-firstShortest PathImproving Best‐FirstBest‐first is often tremendously faster than BFS/Dijkstra, but might stop with a non‐optimal solutionHow can it be modified to be (almost) as fast, but guaranteed to find optimal solutions?A* ‐ Hart, Nilsson, Raphael 1968– One of the first significant algorithms developed in AI– Widely used in many applications9A*• Exactly like Best‐first search, but using a different criteria for the priority queue:• minimize (distance from start) +(estimated distance to goal)• priority f(n) = g(n) + h(n)f(n) = priority of a nodeg(n) = true distance from starth(n) = heuristic distance to goal10Optimality of A*• Suppose the estimated distance is alwaysless than or equal to the true distance to the goal– heuristic is a lower bound• Then: when the goal is removed from the priority queue, we are guaran teed to have found a shortest path!11A* in Action1252ndSt51stSt50thSt10thAve9thAve8thAve7thAve6thAve5thAve4thAve3rdAve2ndAveS G53ndSth=6+2H=1+7h=7+3Application of A*: Speech Recognition• (Simplified) Problem:– System hears a sequence of 3 words– It is unsure about what it heard • For each word, it has a set of possible “guesses”• E.g.: Word 1 is one of { “hi”, “high”, “I” }– What is the most likely sentence it heard?13Speech Recognition as Shortest Path• Convert to a shortest‐path problem:– Utterance is a “layered” DAG– Begins with a special dummy “start” node– Next: A layer of nodes for each word position, one node for each word choice– Edges between every node in layer i to every node in layer i+1• Cost of an edge is smaller if the pair of words frequently occurtogether in real speech– Technically: ‐ log probability of co‐occurrence– Finally: a dummy “end” node– Find shortest path from start to end node1415W11W11W31W41W21W12W22W13W23W33W43Summary: Graph Search• Depth First– Little memory required– Might find non‐optimal path• Breadth First– Much memory required– Always finds optimal path• Iterative Depth‐First Search– Repeated depth‐first searches, little memory required• Dijskstra’s Short Path Algorithm– Like BFS for weighted graphs• Best First– Can visit fewer nodes– Might find non‐optimal path• A*– Can visit fewer nodes than BFS or Dijkstra– Optimal if heuristic estimate is a lower‐bound16Dynamic Programming• Algorithmic technique that systematically recordsthe answers to sub‐problems in a table and re‐usesthose recorded results (rather than re‐computing them).• Simple Example: Calculating the Nth Fibonacci number.Fib(N) = Fib(N‐1) + Fib(N‐2)17Floyd‐Warshall• for (int k = 1; k =< V; k++)• for (int i = 1; i =< V; i++)• for (int j = 1; j =< V; j++)• if ( ( M[i][k]+ M[k][j] ) < M[i][j] )M[i][j] = M[i][k]+ M[k][j] 18Invariant: After the kth iteration, the matrix includes the shortest paths for all pairs of vertices (i,j) containing only vertices 1..k as intermediate verticesabcdea02- -4-b- 0-213c--0-1d---04e----019bcdea-42-21314Initial state of the matrix:M[i][j] = min(M[i][j], M[i][k]+ M[k][j])abcdea020-40b- 0-21-1c--0-1d---04e----020bcdea-42-21314Floyd-Warshall -for All-pairs shortest pathFinal Matrix ContentsCSE 326: Data StructuresNetwork Flow21Network Flows• Given a weighted, directed graph G=(V,E)• Treat the edge weights as capacities• How much can we flow through the graph?22ACBDFHGE17115641213239104I61120Network flow: definitions• Define special source s and sink t vertices• Define a flow as a function on edges:– Capacity: f(v,w) <= c(v,w)– Conservation: for all u except source, sink– Value of a flow: – Saturated edge: when f(v,w) = c(v,w)23∑∈=Vvvuf 0),(∑=vvsff ),(Network flow: definitions• Capacity: you can’t overload an edge• Conservation: Flow entering any vertex must equal flow leaving that vertex• We want to maximize the value of a flow, subject to the above constraints24Network Flows• Given a weighted, directed graph G=(V,E)• Treat the edge weights as capacities• How much can we flow through the graph?25sCBDFHGE17115641213239104t61120A Good Idea that Doesn’t Work• Start flow at 0• “While there’s room for more flow, push more flow across the network!”– While there’s some path from s to t, none of whose edges are saturated– Push more flow along the path until some edge is saturated– Called an “augmenting path”26How do we know there’s still room?• Construct a residual graph: – Same vertices– Edge weights are the “leftover” capacity on the edges– If there is a path sÆt at all, then there is still room27Example (1)28AB CDFE32212244Flow / CapacityInitial graph – no flowExample (2)29AB CDFE0/30/20/20/10/20/20/40/4Flow / CapacityResidual Capacity32412422Include the