Elementary Graph Algorithms: Spanning Trees, Shortest Paths
Document Details
Uploaded by koala24
Tags
Related
Summary
This document provides an overview of elementary graph algorithms, including minimum spanning trees, Kruskal's algorithm, Prim's algorithm and shortest path algorithms like Dijkstra's and the Bellman-Ford algorithm. It also includes examples to help to understand the algorithms.
Full Transcript
ELEMENTARY GRAPH ALGORITHMS Minimum Spanning Trees Spanning tree is a minimal subgraph G' of G such that V(G') = V(G) and G' is connected (by a minimal subgraph, we mean one with the fewest number of edges). When the graph G is connected, a depth first or breadth first search starting at...
ELEMENTARY GRAPH ALGORITHMS Minimum Spanning Trees Spanning tree is a minimal subgraph G' of G such that V(G') = V(G) and G' is connected (by a minimal subgraph, we mean one with the fewest number of edges). When the graph G is connected, a depth first or breadth first search starting at any vertex, visits all the vertices in G The spanning tree resulting from a call to DFS is known as a depth first spanning tree. When BFS is used, the resulting spanning tree is called a breadth first spanning tree 241 ELEMENTARY GRAPH ALGORITHMS Trees and Minimum Cost Spanning Trees Depth first spanning tree Breadth first spanning tree 242 Minimum Cost Spanning Trees To interconnect a set of n pins, we can use an arrangement of n - 1 wires, each connecting two pins. Of all such arrangements, the one that uses the least amount of connection cost is usually the most desirable We can model this connection problem with undirected graph G = (V, E), where V is the set of pins, E is the set of possible interconnections between pairs of edges, and for each edge (u, v) E, we have a weight w(u, v) specifying the cost to connect u and v. We then wish to find an acyclic subset T E that connects all of the vertices and whose total weight w(u,v) is minimized 243 Minimum Cost Spanning Trees One approach to determining a minimum cost spanning tree of a graph has been given by Kruskal. In this approach a minimum cost spanning tree, T, is built edge by edge. Edges are considered for inclusion in T in non-decreasing order of their costs. An edge is included in T if it does not form a cycle with the edges already in T 244 Minimum Cost Spanning Trees 245 Minimum Cost Spanning Trees: Kruskal’s algorithm 246 Minimum Cost Spanning Trees Assignment: Find MST using Kruskal’s algorithm 247 Minimum Cost Spanning Trees Assignment: Find MST using Kruskal’s algorithm One possible solution 248 Minimum Cost Spanning Trees Assignment: Find MST using Kruskal’s algorithm One possible solution 249 Minimum Cost Spanning Trees Assignment: Find MST using Kruskal’s algorithm One possible solution 250 Minimum Cost Spanning Trees Assignment: Find MST using Kruskal’s algorithm One possible solution 251 Minimum Cost Spanning Trees Prim’s Algorithm Prim’s algorithm operates much like Dijkstra’s algorithm for finding shortest paths in a graph, which we see in next lectures. Prim’s algorithm has the property that the edges in the set A always form a single tree. The tree starts from an arbitrary root vertex r and grows until the tree spans all the vertices in V. At each step, a light edge is added to the tree A that connects A to an isolated vertex of GA = (V, A). Prim’s Algorithm 3 D E 5 4 11 2 A 3 B 8 C 9 6 5 7 F 2 G Prim’s Algorithm Select a random vertex for the start Mark incident edges and select the one with min. weight 3 D E 5 4 11 2 A 3 B 8 C 9 6 5 7 F 2 G Prim’s Algorithm Select a random vertex for the start Mark incident edges of A and select the one with min. weight 3 D E 5 4 11 2 A 3 B 8 C 9 6 5 7 F G 2 A 3 B Prim’s Algorithm Mark incident edges of B and select from all marked edges the one with min. weight 3 D E 5 4 11 2 A 3 B C 8 D 9 6 5 7 2 F G 2 A 3 B Prim’s Algorithm Mark incident edges of D and select from all marked edges the one with min. weight 3 D E 5 4 11 2 A 3 B C 3 8 D E 9 6 5 7 2 F G 2 A 3 B Prim’s Algorithm Mark incident edges of E and select from all marked edges the one with min. weight. It is 4 but it create a cycle, rejected. Select next edge with min. weight, 5. 3 D E 5 4 11 2 3 3 B C D E A 8 9 2 6 5 7 F G A 3 B 2 5 G Prim’s Algorithm Mark incident edges of G and select from all marked edges the one with min. weight. 3 D E 5 4 11 2 3 3 B C D E A 8 9 2 6 5 7 F G A 3 B 2 5 F 2 G Prim’s Algorithm Vertex C has the incident edges with weights of 7, 8, 11. Before including C all edges with weights less than 7, 8, 11 has to be verified for spanning tree connection. If any edge creates a cycle, rejected, otherwise it will be included in the tree. Edges 5, 6 less than 7 are rejected and 7 is accepted. 3 D E 5 4 11 2 3 3 B C D E A 8 9 2 6 5 7 B C F 2 G A 3 5 7 F G = 22 2 Shortest Paths In a shortest-paths problem, we are given a weighted, directed graph G = (V, E), with weight function w : E R mapping edges to real-valued weights. The weight of path p = (v0, v1,... , vk ) is the sum of the weights of its constituent edges 261 Relaxation The algorithms discussed here use the relaxation technique. For each vertex v V, we maintain an attribute d[v] We call d[v] a shortest path The process of relaxing an edge (u, v) consists of testing whether we can improve the shortest path to v found so far by going through u and, if so, updating d[v] A relaxation step may decrease the value of the shortest path d[v] The outcome of a relaxation step can be viewed as a relaxation of the constraint d[v] > d[u] + w(u, v) That is, if d[v] < d[u] + w(u, v), there is no "pressure" to satisfy this constraint, so the constraint is "relaxed." 262 Relaxation The following code performs a relaxation step on edge (u, v) 9 6 263 Relaxation using BFS Hamburg Stockholm Saint Malo Amsterdam Copenhagen Paris Frankfurt Rom 264 Relaxation using BFS Hamburg Stockholm Saint Malo 0 1 1 Amsterdam Copenhagen Paris Frankfurt Rom 1 1 265 Relaxation using BFS Hamburg Stockholm 0 Saint Malo 1 1 Amsterdam Copenhagen Paris 2 Frankfurt 2 Rom 1 1 1 2 2 Relaxation 266 Relaxation using BFS Hamburg Stockholm 0 Saint Malo 2 1 1 Amsterdam Copenhagen Paris 2 Frankfurt 2 Rom 1 1 2 2 2 267 Relaxation using BFS Hamburg Stockholm 0 Saint Malo 2 1 1 Amsterdam Copenhagen Paris 2 Frankfurt 2 Rom 1 1 2 2 2 268 Relaxation using BFS Hamburg Stockholm 0 Saint Malo 2 1 1 Amsterdam Copenhagen 3 2 Paris Frankfurt 2 Rom 1 1 2 2 2 3 269 Relaxation using BFS Hamburg Stockholm 0 Saint Malo 2 1 3 1 Amsterdam Copenhagen 3 2 Paris Frankfurt 2 Rom 1 1 2 2 2 3 3 270 Relaxation using BFS Hamburg Stockholm 0 Saint Malo 2 1 3 1 Amsterdam Copenhagen 3 2 Paris Frankfurt 2 Rom 1 1 2 2 2 3 3 271 Relaxation using BFS Hamburg Stockholm 0 Saint Malo 2 1 3 1 Amsterdam Copenhagen 3 2 Paris Frankfurt 2 Rom 1 1 2 2 2 3 3 272 Relaxation using BFS The the value of shortest path is 3350 km Which path is the shortest? One solution is to go backwards to source through all paths to find the minimum value of 3350 km. Hamburg Stockholm Saint Malo Amsterdam Copenhagen Paris Frankfurt Rom 273 Shortest Paths (Dijkstra's algorithm) This algorithm solves the single-source shortest-paths problem on a weighted, directed graph G = (V, E) Definition: for all vertices v S, we have d[v] = (s, v). The algorithm repeatedly selects the vertex u V - S with the minimum shortest- path estimate, inserts u into S, and relaxes all edges leaving u. 274 Shortest Path, Dijkstra's algorithm u v 1 10 9 s 2 3 4 6 7 5 2 x y 275 Shortest Path, Dijkstra's algorithm u v 1 10 s 2 3 9 4 6 7 5 2 x y 276 Shortest Path, Dijkstra's algorithm u v 1 10 s 2 3 9 4 6 5 7 2 x y 277 Shortest Path, Dijkstra's algorithm u v 1 10 9 2 3 s 4 6 7 5 2 x y 278 Shortest Path, Dijkstra's algorithm u v 1 10 9 2 3 s 4 6 7 5 2 x y 279 Shortest Path, Dijkstra's algorithm u v 1 10 9 2 3 s 4 6 7 5 2 x y 280 Assignment: Find the Shortest Paths using Dijkstra's algorithm Solution: https://prezi.com/po0cka9lrrqd/applied-example-of-dijkstras-algorithm 281 Assignment: Find the Shortest Paths using Dijkstra's algorithm 282 Assignment: Solution Find the Shortest Paths using Dijkstra's algorithm 283 Shortest Paths (The Bellman-Ford algorithm) Given is a weighted, directed graph G = (V, E) with source s and weight function w : E R Like Dijkstra's algorithm, the Bellman-Ford algorithm uses the technique of relaxation, progressively decreasing an estimate d[v] on the weight of a shortest path from the source s to each vertex v V until it achieves the actual shortest path weight (s, v). The algorithm returns TRUE if and only if the graph contains no negative-weight cycles that are reachable from the source 284 Shortest Path, Bellman-Ford algorithm A B 1 Select Source S 3 Select Destination T 5 2 S 2 7 T -2 3 10 C D S A B C D T d[v] 0 P[v] 285 Shortest Path, Bellman-Ford algorithm A B Select adjacent vertices to S 1 3 5 2 S 2 7 T -2 3 10 C D S A B C D T d[v] 0 P[v] S S 286 Shortest Path, Bellman-Ford algorithm A B Continue with any relaxed vertex 1 We do here alphabetical 3 Select A 5 2 S 2 7 T -2 3 10 C D S A B C D T d[v] 0 P[v] S S 287 287 Shortest Path, Bellman-Ford algorithm A B Select A 1 3 5 2 S 2 7 T -2 3 10 C D S A B C D T d[v] 0 P[v] S A S 288 288 Shortest Path, Bellman-Ford algorithm A B Select any relaxed vertex 1 Select B 3 Relax adjacent vertices 5 to B; C(already relaxed), 2 D,T S 2 7 T -2 3 10 C D S A B C D T d[v] 0 P[v] S A S B B 289 289 Shortest Path, Bellman-Ford algorithm A B Select any relaxed vertex 1 Select C 3 Relax adjacent vertices 5 to C; A, D 2 S 2 7 T -2 3 10 C D S A B C D T d[v] 0 P[v] S C A S B C B 290 290 Shortest Path, Bellman-Ford algorithm A B Select any relaxed vertex 1 Select D 3 Relax adjacent vertices 5 to D; T(already relaxed) 2 S 2 7 T -2 3 10 Done with first iteration C D S A B C D T d[v] 0 P[v] S C A S B C B 291 291 Shortest Path, Bellman-Ford algorithm A B Bellman-Ford has V-1 iteration 1 We have 6 vertices results to 3 6-1= 5 iterations 5 Relax adjacent vertices 2 to S; A(already relaxed), S 2 7 T C(already relaxed) -2 3 10 C D S A B C D T d[v] 0 P[v] C A S B C B 292 292 Shortest Path, Bellman-Ford algorithm Select A A B Relax adjacent vertices 1 B => 1 3 Select B 5 Relax adjacent vertices 2 C(already relaxed) , D(already relaxed), S 2 7 T T => 4 -2 Select C Relax adjacent vertices 3 10 A(already relaxed) C D D(already relaxed) S A B C D T d[v] 0 P[v] C A S C B 293 293 Shortest Path, Bellman-Ford algorithm Select D A B Relax adjacent vertices 1 T(already relaxed) 3 5 Select T Relax adjacent vertices 2 no adjacent vertices S 2 7 T -2 Repeat the relaxation for 3 10 remaining 3 Iterations from S C D S A B C D T d[v] 0 P[v] C A S C B 294 294 Shortest Path, Bellman-Ford algorithm Repeat the relaxation for remaining 3 Iterations from S A B 1 3 5 S 2 2 7 T -2 3 10 C D If the d[v] still changes after n iterations (# of Vertices, here is 6) then the Bellman Ford can not find the shortest path. The graph has a negative cycle. 295 295 Shortest Path, Bellman-Ford algorithm A B 1 3 5 S 2 2 7 T -2 3 10 C D Last step is finding the shortest path Return backwards from Destination T to Source S. If valid returns 0 in S T=4: to D returns 4-10=1 (invalid), to B returns 4-3=1 (Valid) 296 296 Shortest Path, Bellman-Ford algorithm A B 1 3 5 S 2 2 7 T -2 3 10 C D B=1: to A returns 1-1=0 (Valid) A=0: Shortest path is to S returns 0-5=0 (Valid) to C returns 0-2=-2 (Valid) T B A C S C=1: to S returns -2-(-2)=0 (Valid) 297 297 Shortest Path, Bellman-Ford algorithm Assignment: s to z 298 Shortest Path, Bellman-Ford algorithm Solution 299 Shortest Path, Bellman-Ford algorithm t 5 x -2 6 -3 s 8 -4 7 2 7 9 y z 300 Shortest Path, Bellman-Ford algorithm t 5 x -2 6 -3 s 8 -4 7 2 7 9 y z 301 Shortest Path, Bellman-Ford algorithm t 5 x -2 6 -3 s 8 -4 7 2 7 9 y z 302
