Shortest Path Algorithms PDF

SHORTEST-PATH ALGORITHMS Finding shortest paths in weighted graphs is one of the most important problems. 1  SHORTEST-PATH ALGORITHMS Finding shortest paths in weighted graphs is one of the most important problems. – The input is a weighted gra...

SHORTEST-PATH ALGORITHMS Finding shortest paths in weighted graphs is one of the most important problems. 1  SHORTEST-PATH ALGORITHMS Finding shortest paths in weighted graphs is one of the most important problems. – The input is a weighted graph: associated with each edge (vi, vj) is a cost cij. 2  SHORTEST-PATH ALGORITHMS Finding shortest paths in weighted graphs is one of the most important problems. – The input is a weighted graph: associated with each edge (vi, vj) is a cost cij. N −1 – The cost of a path v1,v2,v3,...,v N cis i ,i +1 i =1 this is called as the weighted path length (the unweighted path length is just N-1) 3 SHORTEST-PATH ALGORITHMS 2 v1 v2 4 1 3 10 2 2 v3 v4 v5 8 4 6 5 1 v6 v7 4 SHORTEST-PATH ALGORITHMS 2 v1 v2 4 1 3 10 2 2 v3 v4 v5 8 4 6 5 1 v6 v7 Cost = 1+8 = 9 5 SHORTEST-PATH ALGORITHMS 2 v1 v2 4 1 3 10 2 2 v3 v4 v5 8 4 6 5 1 v6 v7 Cost = 2+10+6+1 = 19 6 SHORTEST-PATH ALGORITHMS 2 v1 v2 4 1 3 10 2 2 v3 v4 v5 8 4 6 5 1 v6 v7 Cost = 2+3+4+1 = 10 7 SHORTEST-PATH ALGORITHMS 2 v1 v2 4 1 3 10 2 2 v3 v4 v5 8 4 6 5 1 v6 v7 Cost = 2+3+2+6 +1= 14 8 SHORTEST-PATH ALGORITHMS 2 v1 v2 4 1 3 10 2 2 v3 v4 v5 8 4 6 5 1 v6 v7....... Cost = 1+4+1= 6 (Shortest Path) 9  SHORTEST-PATH ALGORITHMS Edges with negative costs may cause problems! 2 v1 v2 4 1 3 –10 2 1 v3 v4 v5 6 2 6 5 1 v6 v7 10  SHORTEST-PATH ALGORITHMS Edges with negative costs may cause problems! 2 v1 v2 4 1 3 –10 2 1 v3 v4 v5 6 2 6 5 1 v6 v7 11  SHORTEST-PATH ALGORITHMS Edges with negative costs will cause problems! 2 v1 v2 4 1 3 –10 2 1 v3 v4 v5 6 2 6 5 1 v6 v7 Cost = 1+3 –10 + 1 = –5 12  SHORTEST-PATH ALGORITHMS Edges with negative costs will cause problems! 2 v1 v2 4 1 3 –10 2 1 v3 v4 v5 6 2 6 5 1 v6 v7 Cost = 1+3 –10+1 = –5, in fact we can go around the cycle any number of times and cost would be less and less! 13  SHORTEST-PATH ALGORITHMS Edges with negative costs will cause problems! 2 v1 v2 4 1 3 –10 2 1 v3 v4 v5 6 2 6 5 1 v6 v7 Negative cost cycle 14  SHORTEST-PATH ALGORITHMS Edges with negative costs will cause problems! 2 v1 v2 4 1 3 –10 2 1 v3 v4 v5 6 2 6 5 1 v6 v7 Negative cost cycle Shortest paths are not defined if there is such a cycle. 15  SHORTEST-PATH APPLICATIONS Find the shortest route to fly from Istanbul to New York. 16  SHORTEST-PATH APPLICATIONS Find the shortest route to fly from Istanbul to New York. – Least time including waits at the airports 17  SHORTEST-PATH APPLICATIONS Find the shortest route to fly from Istanbul to New York. – Least time including waits at the airports – Cheapest total flight (assuming flight cost is additive) 18  SHORTEST-PATH APPLICATIONS Least cost/time to transmit data through computer networks. – Costs capture data rate, or TL/106 bytes, etc. 19  SHORTEST-PATH ALGORITHMS 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. 20  SHORTEST-PATH ALGORITHMS 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. – Finding the shortest path to only ONE other vertex is not any easier, asymptotically. 21 UNWEIGHTED SHORTEST PATHS v1 v2 v3 v4 v5 v6 v7 Just like the general problem except all costs are 1! 22 UNWEIGHTED SHORTEST PATHS v1 v2 s v3 v4 v5 v6 v7 Suppose we want to shortest paths from s=v3 23 UNWEIGHTED SHORTEST PATHS v1 v2 s v3 v4 v5 0 v6 v7 From v3 to v3 shortest path is 0 24 UNWEIGHTED SHORTEST PATHS 1 v1 v2 s v3 v4 v5 0 v6 v7 1 Let us consider vertices 1 away. 25 UNWEIGHTED SHORTEST PATHS 1 v1 v2 s v3 v4 v5 0 v6 v7 1 Let us consider vertices 2 away by considering yet unknown vertices that are 1 away from v1 and v6 26 UNWEIGHTED SHORTEST PATHS 1 2 v1 v2 s v3 v4 v5 2 0 v6 v7 1 Let us consider vertices 2 away by considering yet unknown vertices that are 1 away from v1 and v6 27 UNWEIGHTED SHORTEST PATHS 1 2 v1 v2 s v3 v4 v5 2 0 v6 v7 1 Let us consider vertices 2 away by considering yet unknown vertices that are 1 away from v1 and v6 28 UNWEIGHTED SHORTEST PATHS 1 2 v1 v2 s v3 v4 v5 2 0 v6 v7 1 Let us consider vertices 3 away by considering yet unknown vertices that are 1 away from v2 and v4 29 UNWEIGHTED SHORTEST PATHS 1 2 v1 v2 3 s v3 v4 v5 2 0 v6 v7 1 Let us consider vertices 3 away by considering yet unknown vertices that are 1 away from v2 and v4 30 UNWEIGHTED SHORTEST PATHS 1 2 v1 v2 3 s v3 v4 v5 2 0 v6 v7 3 1 Let us consider vertices 3 away by considering yet unknown vertices that are 1 away from v2 and v4 31 UNWEIGHTED SHORTEST PATHS 1 2 v1 v2 3 s v3 v4 v5 2 0 v6 v7 3 1 Final shortest paths from s 32 UNWEIGHTED SHORTEST PATHS 1 2 v1 v2 3 s v3 v4 v5 2 0 v6 v7 3 1 This strategy is known as breadth-first search 33 UNWEIGHTED SHORTEST PATHS 1 2 v1 v2 3 s v3 v4 v5 2 0 v6 v7 3 1 This strategy is known as breadth-first search The edges make up the breadth-first search tree 34  IMPLEMENTATION For each vertex we keep three pieces of information: – known is a boolean F if the shortest distance is not yet known T if the shortest distance is known – dist is an integer  if a vertex is yet not known, or it is not reachable from s – path is an integer used to construct the shortest path 35  IMPLEMENTATION void Graph::unweighted (Vertex s) { Vertex v, w; s.dist = 0; // check all possible distances for (int currDist = 0; currDist < NUM_VERTICES; currDist++) // locate all not known vertices at the current distance for each vertex v if (!v.known && v.dist == currDist) { // mark vertex as known v.known = true; // Compute distances to neighboring vert. for each w adjacent to v if (w.dist == INFINITY) { w.dist = currDist+1; w.path = v; } } } 36  IMPLEMENTATION void Graph::unweighted (Vertex s) { Vertex v, w; s.dist = 0; // check all possible distances for (int currDist = 0; currDist < NUM_VERTICES; currDist++) // locate all not known vertices at the current distance for each vertex v O(|V|) if (!v.known && v.dist == currDist) { // mark vertex as known v.known = true; O(|V| ) O(|V|) 2 // Compute distances to neighboring vert. for each w adjacent to v if (w.dist == INFINITY) { w.dist = currDist+1; O(|E|) } w.path = v; } } If finding the vertex with distance currDist takes O(V) time, then O(|E|+ |V|2) = 37  IMPROVING THE ALGORITHM Just like in topological sort, the inefficiency stems from sequential search of the vertices. 38  IMPROVING THE ALGORITHM Just like in topological sort, the inefficiency stems from sequential search of the vertices. We can again use a queue to locate vertices efficiently. 39  IMPROVING THE ALGORITHM A queue where vertices are queued in order of distance from s At the start of an iteration, which will visit all the vertices that are at distance d from s vxjik v...ykj v...... k x vxy... at at at at distance distance distance distance at distance at distance dd+from d sfrom d1 from from s ds + d1 +from 1 from s s s 40  FASTER IMPLEMENTATION Void Graph::unweighted (Vertex s) { Queue q(NUM_VERTICES); Vertex v, w; q.enqueue (s); s.dist = 0; O(|E|+ |V|) = O(|E|) while(! q.isEmpty( )) { v = q.dequeue( ); v.known = true O(|V|) for each w adjacent to v if (w.dist == INFINITY) { w.dist = v.dist + 1; w.path = v; O(|E|) q.enqueue (w); } } } Note1: Vertices are queued in order of distance from s Note2: If queue becomes empty prematurely, this indicates there are nodes that are not reachable from the start node s. 41  WEIGHTED SHORTEST PATH Shortest path (least cost, on a weighted graph) from a distinguished vertex s to another vertex 42 WEIGHTED SHORTEST PATH 2 v1 v2 4 1 3 10 2 2 v3 v4 v5 8 4 6 5 1 v6 v7 43  WEIGHTED SHORTEST PATH Dijkstra’s algorithm calculates shortest paths from a given vertex to all the other vertices. 44  WEIGHTED SHORTEST PATH Dijkstra’s algorithm calculates shortest paths from a given vertex to all the other vertices. There are no known algorithms that find the shortest path from a vertex s to another vertex v faster (by more than a constant factor) than finding the shortest path from s to all the other vertices 45  DIJKSTRA’S ALGORITHM Partition the nodes into two sets: – Known nodes Minimum distance from the initial node is known. 46  DIJKSTRA’S ALGORITHM Partition the nodes into two sets: – Known nodes Minimum distance from the initial node is known. – Unknown nodes Minimum distance from the initial node is unknown, at least, not finalized 47  DIJKSTRA’S ALGORITHM Variables used in the algorithm: – v.known: Boolean, true → we have a guarantee that no shorter path will be found to the vertex v – dv (v.dist): tentative path to vertex v using (passing through) only the known vertices – pv (v.path): last vertex to cause a change to dv (indicating where the shortest path so far comes from) 48  DIJKSTRA’S ALGORITHM Basic Idea – Initially, all nodes are marked as unknown s is at distance 0 from itself All others are at distance ∞ from s. – Among each of the (remaining) unknown nodes Pick the one with the minimum distance Mark it as known For all nodes adjacent to the node just selected – Update the distances to the unknown nodes if there is now a shorter path through the newly selected node – Also remember how you come to the node. 49  Dijkstra’s Algorithm At each step, choose a vertex v with the smallest dv among all the unknown vertices Make vertex v known Update dw and pw for other adjacent unknown vertices w if v gives a shorter path to vertex w 50  DIJKSTRA’S ALGORITHM Update dw for the unknown vertices w if v gives a shorter path to vertex w that is, if dw > dv + Cv,w 51  DIJKSTRA’S ALGORITHM Update dw for the unknown vertices w if v gives a shorter path to vertex w that is, if dw > dv + Cv,w Update – dw = dv + Cv,w (new shorter distance to w) – pw = v ( from v ) 52 DIJKSTRA’S ALGORITHM 2 v1 v2 4 1 3 10 2 2 v3 v4 v5 8 4 6 5 1 v6 v7 53  DIJKSTRA’S ALGORITHM ∞ ( ?) 2 ∞ ( ?) v1 v2 4 1 3 10 2 2 0 ( 3) v3 v4 v5 ∞ ( ?) ∞ ( ?) 8 4 6 5 1 v6 v7 ∞ ( ?) ∞ ( ?) X (Y) Known node, dist is X, previous node is Y 54  DIJKSTRA’S ALGORITHM ∞ ( ?) 2 ∞ ( ?) v1 v2 4 1 3 10 2 2 0 ( 3) v3 v4 v5 ∞ ( ?) ∞ ( ?) 8 4 6 5 1 v6 v7 ∞ ( ?) ∞ ( ?) 55  DIJKSTRA’S ALGORITHM ∞ ( ?) 2 4 ( 3) v1 v2 4 1 3 10 2 2 0 ( 3) v3 v4 v5 ∞ ( ?) ∞ ( ?) 8 4 6 5 1 v6 v7 ∞ ( ?) ∞ ( ?) 56  DIJKSTRA’S ALGORITHM ∞ ( ?) 2 4 ( 3) v1 v2 4 1 3 10 2 2 0 ( 3) v3 v4 v5 ∞ ( ?) 2 ( 3) 8 4 6 5 1 v6 v7 ∞ ( ?) ∞ ( ?) 57  DIJKSTRA’S ALGORITHM ∞ ( ?) 2 4 ( 3) v1 v2 4 1 3 10 2 2 0 ( 3) v3 v4 v5 ∞ ( ?) 2 ( 3) 8 4 6 5 1 v6 v7 ∞ ( ?) 5 ( 3) 58  DIJKSTRA’S ALGORITHM ∞ ( ?) 2 4 ( 3) v1 v2 4 1 3 10 2 2 0 ( 3) v3 v4 v5 ∞ ( ?) 2 ( 3) 8 4 6 5 1 v6 v7 ∞ ( ?) 5 ( 3) 59  DIJKSTRA’S ALGORITHM ∞ ( ?) 2 4 ( 3) v1 v2 4 1 3 10 2 2 0 ( 3) v3 v4 v5 ∞ ( ?) 2 ( 3) 8 4 6 5 1 v6 v7 ∞ ( ?) 5 ( 3) 60  DIJKSTRA’S ALGORITHM ∞ ( ?) 2 4 ( 3) v1 v2 4 1 3 10 2 2 0 ( 3) v3 v4 v5 ∞ ( ?) 2 ( 3) 8 4 6 5 1 v6 v7 ∞ ( ?) 5 ( 3) 61  DIJKSTRA’S ALGORITHM ∞ ( ?) 2 3( 4) v1 v2 4 1 3 10 2 2 0 ( 3) v3 v4 v5 ∞ ( ?) 2 ( 3) 8 4 6 5 1 v6 v7 ∞ ( ?) 5 ( 3) 62  DIJKSTRA’S ALGORITHM 5 ( 4) 2 3( 4) v1 v2 4 1 3 10 2 2 0 ( 3) v3 v4 v5 ∞ ( ?) 2 ( 3) 8 4 6 5 1 v6 v7 ∞ ( ?) 5 ( 3) 63  DIJKSTRA’S ALGORITHM 5 ( 4) 2 3( 4) v1 v2 4 1 3 10 2 2 0 ( 3) v3 v4 v5 4 ( 4) 2 ( 3) 8 4 6 5 1 v6 v7 ∞ ( ?) 5 ( 3) 64  DIJKSTRA’S ALGORITHM 5 ( 4) 2 3( 4) v1 v2 4 1 3 10 2 2 0 ( 3) v3 v4 v5 4 ( 4) 2 ( 3) 8 4 6 5 1 v6 v7 6 ( 4) 5 ( 3) 65  DIJKSTRA’S ALGORITHM 5 ( 4) 2 3( 4) v1 v2 4 1 3 10 2 2 0 ( 3) v3 v4 v5 4 ( 4) 2 ( 3) 8 4 6 5 1 v6 v7 6 ( 4) 5 ( 3) 66  DIJKSTRA’S ALGORITHM 5 ( 4) 2 3( 4) v1 v2 4 1 3 10 2 2 0 ( 3) v3 v4 v5 4 ( 4) 2 ( 3) 8 4 6 5 1 v6 v7 6 ( 4) 5 ( 3) 67  DIJKSTRA’S ALGORITHM 5 ( 4) 2 3( 4) v1 v2 4 1 3 10 2 2 0 ( 3) v3 v4 v5 4 ( 4) 2 ( 3) 8 4 6 5 1 v6 v7 6 ( 4) 5 ( 3) 68  DIJKSTRA’S ALGORITHM 5 ( 4) 2 3( 4) v1 v2 4 1 3 10 2 2 0 ( 3) v3 v4 v5 4 ( 4) 2 ( 3) 8 4 6 5 1 v6 v7 6 ( 4) 5 ( 3) 69  DIJKSTRA’S ALGORITHM 5 ( 4) 2 3( 4) v1 v2 4 1 3 10 2 2 0 ( 3) v3 v4 v5 4 ( 4) 2 ( 3) 8 4 6 5 1 v6 v7 6 ( 4) 5 ( 3) 70  DIJKSTRA’S ALGORITHM 5 ( 4) 2 3( 4) v1 v2 4 1 3 10 2 2 0 ( 3) v3 v4 v5 4 ( 4) 2 ( 3) 8 4 6 5 1 v6 v7 6 ( 4) 5 ( 3) 71  DIJKSTRA’S ALGORITHM 5 ( 4) 2 3( 4) v1 v2 4 1 3 10 2 2 0 ( 3) v3 v4 v5 4 ( 4) 2 ( 3) 8 4 6 5 1 v6 v7 6 ( 4) 5 ( 3) 72  DIJKSTRA’S ALGORITHM 5 ( 4) 2 3( 4) v1 v2 4 1 3 10 2 2 0 ( 3) v3 v4 v5 4 ( 4) 2 ( 3) 8 4 6 5 1 v6 v7 6 ( 4) 5 ( 3) 73  DIJKSTRA’S ALGORITHM 5 ( 4) 2 3( 4) v1 v2 4 1 3 10 2 2 0 ( 3) v3 v4 v5 4 ( 4) 2 ( 3) 8 4 6 5 1 v6 v7 6 ( 4) 5 ( 3) 74  DIJKSTRA’S ALGORITHM 5 ( 4) 2 3( 4) v1 v2 4 1 3 10 2 2 0 ( 3) v3 v4 v5 4 ( 4) 2 ( 3) 8 4 6 5 1 v6 v7 6 ( 4) 5 ( 3) 75  DIJKSTRA’S ALGORITHM 5 ( 4) 2 3( 4) v1 v2 4 1 3 10 2 2 0 ( 3) v3 v4 v5 4 ( 4) 2 ( 3) 8 4 6 5 1 v6 v7 6 ( 4) 5 ( 3) 76  DIJKSTRA’S ALGORITHM 5 ( 4) 2 3( 4) v1 v2 4 1 3 10 2 2 0 ( 3) v3 v4 v5 4 ( 4) 2 ( 3) 8 4 6 5 1 v6 v7 6 ( 4) 5 ( 3) 77  DIJKSTRA’S ALGORITHM 5 ( 4) 2 3( 4) v1 v2 4 1 3 10 2 2 0 ( 3) v3 v4 v5 4 ( 4) 2 ( 3) 8 4 6 5 1 v6 v7 6 ( 4) 5 ( 3) 78  DIJKSTRA’S ALGORITHM 5 ( 4) 2 3( 4) v1 v2 4 1 3 10 2 2 0 ( 3) v3 v4 v5 4 ( 4) 2 ( 3) 8 4 6 5 1 v6 v7 6 ( 4) 5 ( 3) 79  DIJKSTRA’S ALGORITHM 5 ( 4) 2 3( 4) v1 v2 4 1 3 10 2 2 0 ( 3) v3 v4 v5 4 ( 4) 2 ( 3) 8 4 6 5 1 v6 v7 6 ( 4) 5 ( 3) Shortest path to V2 = V3 – V4 – V2 80  DIJKSTRA’S ALGORITHM void Graph::dijkstra(Vertex s) s.dist = 0; O(|V|) for (; ; ) { v = smallest unknown distance vertex if (v == NOT_A_VERTEX) O(|V|) break; v.known = true; O(|V2|) for each w adjacent to v if ( !w.known) if (v.dist + Cvw < w.dist){ O(|E|) decrease(w.dist to v.dist + Cvw ); w.path = v; } If finding a vertex with minimum distance takes O(V) time, then O(|E|+ |V|2) = O(|V|2) 81  RUNNING TIME Scan the graph to find min. dv at each step: – O(|V|) to find the minimum – O(|V|2) total Time to update dw is constant One update per edge for a total of O(|E|) – TOTAL: O(|E|+ |V|2) = O(|V|2) 82  RUNNING TIME TOTAL: O(|E|+ |V|2) = O(|V|2) If the graph is dense |E| = Q(|V|2), this algorithm is simple and essentially optimal If the graph is sparse |E| = Q(|V|), this implementation is too slow. The distances need to be kept in a priority queue. 83  USING A PRIORITY QUEUE Insert the vertices on a priority queue with their dv value used as the ordering function – Outer loop: |V| times – findmin can be done by a deletemin: O(log|V|) – decrease as decreasekey: O(log|V|) each - as many as |E| of them Total: O(|V|log|V|+|E|log|V| ) = O(|E|log|V|) 84  USING A PRIORITY QUEUE void Graph::dijkstra(Vertex s) s.dist = 0; O(log |V|) O(|V||log V|) for (; ; ) { v = smallest unknown distance vertex if (v == NOT_A_VERTEX) O(|V|) break; v.known = true; for each w adjacent to v if ( !w.known) if (v.dist + Cvw < w.dist){ O(|E|) decrease(w.dist to v.dist + Cvw ); w.path = v; O(|E| log |V|) } O(log |V|) O(|V| log |V| + |E| log |V|) = O(|E| log |V|) 85  USING A PRIORITY QUEUE Alternative Instead of finding where each vertex is on the heap and using the decreasekey operation as in the previous example, Just insert the vertices and the new dv values at each decrease operation, on the priority queue with their dv value used as the ordering function 86  USING A PRIORITY QUEUE (Alternative) void Graph::dijkstra(Vertex s) s.dist = 0; O(|E| log |E|) for (; ; ) { v = smallest unknown distance vertex if (v == NOT_A_VERTEX) break; v.known = true; for each w adjacent to v if ( !w.known) if (v.dist + Cvw < w.dist){ O(|E|) decrease(w.dist to v.dist + Cvw ); w.path = v; O(|E| log |E|) } O(log |E|) O(|E| log |E| + |E| log |E|) = O(|E| log |E|) previous complexity = O(|E| log |V|) 87  USING A PRIORITY QUEUE Multiple copies of the same vertex may exist – Outer loop: |V| times – Size of the heap may get too large: O(|E|) – findmin can be done by deletemin operations (until an unknown vertex is found): – Total time |E| O(log|E|) 88  USING A PRIORITY QUEUE decrease(): add a new vertex to the heap and percolate up – O(log|E|) each – Total: O(|E|log|E|) – For sparse graphs, |E| ≤ |V|2 → log |E| ≤ 2log|V| So the total is O(|E|log|V|) - same as the previous priority queue implementation but without using the decreasekey operation 89  DIJKSTRA’S ALGORITHM Printing the Path To find the path from the start vertex s to a vertex w, write a recursive routine that will follow the path variables 90  PRINTING THE PATH void Graph::printPath(Vertex v){ if (v.path != v) { printPath (v.path) ; cout PON(u) Forward arc – If PON(v) < PON(u) && PRE(v) > PRE(u) Cross arc – If not tree, backward, and forward arc 156 DFS ON UNDIRECTED GRAPHS DFS partitions the arcs of an undirected graph into Tree arcs and Backward arcs Consider an arc from u to v – Tree arc If leads to unvisited node i.e., if dfs(u) calls dfs(v) – Backward arc If not tree arc 157  APPLICATIONS OF DFS Finding Cycles – Assign post-order-numbers to each vertex in O(|E| + |V|) time. – Examine all arcs in O(|E|) time. If there is an arc (u,v) such that PON(v) > PON(u) then there is a cycle. 158  APPLICATIONS OF DFS Topogical sorting – The graph has no cycles (which you can test by the previous procedure), – Slightly change the DFS so that you also push the nodes onto a stack AFTER you assign a post-order-number – At the end, the stack has nodes in reverse topological order. 159  APPLICATIONS OF DFS Reachability: Can I get to node v from node u? Start from node u, and perform a DFS. When DFS completes, check if v is visited. – You can not reach v, from u, if it has NOT been visited during DFS 160  CONNECTED COMPONENTS A connected component of an undirected graph is a subgraph in which any two vertices are connected to each other by paths, and which is connected to no additional vertices in the rest of the graph. 161 CONNECTED COMPONENTS g a b d h c e f i 162  CONNECTED COMPONENTS Repeat until no unvisited nodes remain Find the first/next unvisited node. – Mark it as the representative of a connected component – DFS from that node marking everything as visited. Connectedness is an equivalence relation! 163  ROADMAP Algorithmic Paradigms – Divide and Conquer – Greedy – Dynamic Programming 164