```Chapter 14
Weighted Graphs
1
Weighted Graphs
 Weighted Graphs
 Similar to directional Graphs
 Added attribute called “weight” to the edges

Used to designate a preference between edges


What is the minimum spanning tree for a weighted graph?
What is the shortest (or cheapest) distance from one vertex to
another?
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
3
Minimum Spanning Trees
Colina
Pick a vertex
6
10
Bordo
Identify the lightest
Edge from this vertex
New
Vertex in
MSP
No
Identify the next
lightest Edge from
this vertex
Flor
7
5
7
6
7
Ajo
4
8
Danza
Erizo
12
Repeat until no more
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
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
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
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
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
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
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.
11
Minimum Spanning Trees
Colina
6
10
Flor
Bordo
7
5
7
6
7
Ajo
4
8
Danza
Erizo
12
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
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
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.
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
16
All-pairs Shortest Path
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
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
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.
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
Ajo
Ajo
Bordo
Colina
Dansa
6
16
12
4
10
7
Bordo
Colina
Dansa
Erizo
Flor
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.
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.
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.
23
Directional Weighted Graph
Colina
\$6
\$10
Bordo
Flor
\$7
\$3
\$7
\$6
Ajo
\$7
\$4
\$8
Danza
Erizo
\$12
24
```