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