Chapter 14 Weighted Graphs © John Urrutia 2014, All Rights Reserved 1 Weighted Graphs Weighted Graphs Similar to directional Graphs Added attribute called “weight” to the edges Used to designate a preference between edges Helps answer questions like What is the minimum spanning tree for a weighted graph? What is the shortest (or cheapest) distance from one vertex to another? © John Urrutia 2014, All Rights Reserved 2 Minimum Spanning Tree with weighted graphs Weight changes everything Each vertex edge must be compared based on their weight The lightest weight wins Given 6 cities where the weight between each city is the cost ($millions)of building an internet cable What is/are the least expensive route © John Urrutia 2014, All Rights Reserved 3 Minimum Spanning Trees Colina Pick a vertex 6 10 Bordo Add vertex to MSP Identify the lightest Edge from this vertex New Vertex in MSP No Identify the next lightest Edge from this vertex © John Urrutia 2014, All Rights Reserved Flor 7 5 7 6 7 Ajo 4 8 Danza Erizo 12 Repeat until no more Vertices to add 4 Minimum Spanning Trees Erizo Colina 5 6 Flor Bordo Ajo Danza 7 6 4 Colina 6 10 Bordo Flor 7 5 7 6 7 Ajo 4 8 Danza Erizo 12 © John Urrutia 2014, All Rights Reserved 5 Minimum Spanning Trees Flor Colina Erizo Bordo Ajo 6 5 7 6 4 Danza Colina 6 10 Bordo Flor 7 5 7 6 7 Ajo 4 8 Danza Erizo 12 © John Urrutia 2014, All Rights Reserved 6 Minimum Spanning Trees Colina Erizo Flor Bordo Ajo 5 6 7 6 4 Danza Colina 6 10 Bordo Flor 7 5 7 6 7 Ajo 4 8 Danza Erizo 12 © John Urrutia 2014, All Rights Reserved 7 Minimum Spanning Trees Bordo Ajo Danza Erizo Colina 6 4 7 5 6 Flor Colina 6 10 Bordo Flor 7 5 7 6 7 Ajo 4 8 Danza Erizo 12 © John Urrutia 2014, All Rights Reserved 8 Minimum Spanning Trees Ajo Danza Bordo Erizo Colina 4 6 7 5 6 Flor Colina 6 10 Bordo Flor 7 5 7 6 7 Ajo 4 8 Danza Erizo 12 © John Urrutia 2014, All Rights Reserved 9 Minimum Spanning Trees Danza Ajo Bordo Erizo Colina 4 6 7 5 6 Flor Colina 6 10 Bordo Flor 7 5 7 6 7 Ajo 4 8 Danza Erizo 12 © John Urrutia 2014, All Rights Reserved 10 Minimum Spanning Tree The Algorithm Select a current vertex to start the tree Find all edges from the current vertex to vertices not already in the tree. Place them into a priority queue. Select the lowest priority edge from the queue add it and the destination vertex to the tree. Repeat until no more vertices to add. © John Urrutia 2014, All Rights Reserved 11 Minimum Spanning Trees Colina 6 10 Flor Bordo 7 5 7 6 7 Ajo 4 8 Danza Erizo 12 © John Urrutia 2014, All Rights Reserved Ajo Danza Bordo Erizo Colina 4 6 7 5 6 Vertex List Priority Queue A D4 B6 E7 C5 F6 C10 E12 B6 F7 E7 C5 C8 D4 B7 B6 Flor 12 Shortest Path Problem With the Minimum Spanning Tree we answer the question: Can we get there from here With the Shortest Path we answer the questions: What is the shortest way to get there from here © John Urrutia 2014, All Rights Reserved 13 Dijkstra’s Algorithm Developed in 1959 by Edsger Dijkstra Based on an adjacency matrix for a directed graph Finds the shortest path between one vertex to another Finds the shortest paths between a vertex and all other vertices Similar to Warshall’s algorithm but updates a path when it is shorter than a previous one © John Urrutia 2014, All Rights Reserved 14 Dijkstra’s Algorithm For each unvisited vertex in the weighted graph Select the vertex with the smallest total distance Calculate the distance through this vertex to each unvisited neighboring vertex Update the neighboring vertex distance if smaller. Mark the source vertex as visited. © John Urrutia 2014, All Rights Reserved 15 Shortest Path Array 12 3 ==13 15 6 + 10 7 16 <!< 1612 4Update NoChg NoChg 12 ~ Colina $6 $10 ~ 6 Bordo Flor $7 $3 $7 $6 Ajo 0 18 ~ $7 $4 $8 Danza Erizo $12 15 16 ~ ~4 © John Urrutia 2014, All Rights Reserved 16 All-pairs Shortest Path Weighted Adjacency Matrix From / To Ajo Bordo Colina Danza Erizo Flor Ajo inf $6 inf $4 inf inf Bordo inf inf $10 $7 inf inf Colina inf inf inf inf $3 $6 Danza inf inf $8 inf $12 inf Erizo inf $7 inf inf inf inf Flor inf inf inf inf $7 inf © John Urrutia 2014, All Rights Reserved 17 All-pairs Shortest Path All-Pairs Table From / To Ajo Bordo Colina Danza Erizo Flor Ajo inf $6 $12 $4 $16 $18 Bordo inf inf $10 $7 $13 $16 Colina inf $10 inf $17 $3 $6 Danza inf $18 $8 inf $12 $14 Erizo inf $7 $17 $14 inf $23 Flor inf $14 $24 $21 $7 inf © John Urrutia 2014, All Rights Reserved 18 Floyd’s Algorithm Dijkstra’s algorithm for producing the All-Pairs Shortest Path Table runs in O(N2) Floyds algorithm for the All-Pairs Shortest Path Table is more efficient because it uses a variation on Warshall’s algorithm. © John Urrutia 2014, All Rights Reserved 19 Floyd’s Algorithm Process each row and column Ajo goes to Bordo – Bordo goes to? 4Ajo + 7 8 = 13 12 Nothing goes to6 !< < 16 4 No Update Chg Adjacency Matrix Ajo Ajo Bordo Colina Dansa 6 16 12 4 10 7 Bordo Colina Dansa Erizo Flor © John Urrutia 2014, All Rights Reserved 8 Erizo Flor 3 6 12 7 7 20 Summary In a weighted graph, edges have an associated number called the weight, which might represent distances, costs, times, or other quantities. The minimum spanning tree in a weighted graph minimizes the weights of the edges necessary to connect all the vertices. An algorithm using a priority queue can be used to find the minimum spanning tree of a weighted graph. The minimum spanning tree of a weighted graph models real-world situations such as installing utility cables between cities. © John Urrutia 2014, All Rights Reserved 21 Summary The shortest-path problem in a non-weighted graph involves finding the minimum number of edges between two vertices. Solving the shortest-path problem for weighted graphs yields the path with the minimum total edge weight. The shortest-path problem for weighted graphs can be solved with Dijkstra’s algorithm. The algorithms for large, sparse graphs generally run much faster if the adja- cency-list representation of the graph is used rather than the adjacency matrix. © John Urrutia 2014, All Rights Reserved 22 Summary The all-pairs shortest-path problem is to find the total weight of the edges between every pair of vertices in a graph. Floyd’s algorithm can be used to solve this problem. Some graph algorithms take exponential time and are therefore not practical for graphs with more than a few vertices. © John Urrutia 2014, All Rights Reserved 23 Directional Weighted Graph Colina $6 $10 Bordo Flor $7 $3 $7 $6 Ajo $7 $4 © John Urrutia 2014, All Rights Reserved $8 Danza Erizo $12 24

Descargar
# Chap14 Weighted Graphs