Class Notes (1,049,953)
CA (601,044)
(14)
Graves (3)
Lecture 11

MATH 26507 Lecture Notes - Lecture 11: OclcPremium

3 pages85 viewsWinter 2016

Department
Faculty of Applied Science & Technology
Course Code
MATH 26507
Professor
Graves
Lecture
11

This preview shows half of the first page. to view the full 3 pages of the document.
Discrete Math-In Class Exercise
Find the path of min length from X to Y using the breadth first-search algorithm. Show
all steps required to determine shortest path.
Initial set of visited vertices: L = nullset, or 0(strikethrough), u=X(initial vertex),
length(u)=0
vertices adjacent to X are A, B so L={A,B}, each with length 1
remove A from set L, so u=A
vertices adjacent to A that are not in L are B,C
L={B,C} so u=B
vertices adjacent to B that are not in L are C,D
L={C,D} so u=C
vertices adjacent to C that are not in L are D,E
L={D,E} so u=D
vertices adjacent to D that are not in L are E,F
L={E,F} so u=E
vertices adjacent to E that are not in L are F,Y
L={F,Y} and Y is the element of L
The shortest path from X to Y is X->B->D->E->Y
Each time we cross a vertex then we add 1, so 1, 2, 3, 4
The length of the shortest path is 4.
in dykstra's algorithm, "parent" means how we got there
cost to get to a is 0 because we are starting there
set u to vertex with lowest cost
remove u from the set, which becomes {b,c,d,e,z}-refer to example 1.1 from textbook
Exercise:
Find the shortest path from Seattle to Miami using Dijkstra’s
algorithm.
Set of vertices, S={Se,LA,De,Ch,Da,NY,Mi}
vtx Se LA De Ch Da NY Mi
parent Nil Nil Nil Nil Nil Nil Nil
cost 0 Inf Inf Inf Inf Inf inf
find more resources at oneclass.com
find more resources at oneclass.com
You're Reading a Preview

Unlock to view full version

Subscribers Only

Loved by over 2.2 million students

Over 90% improved by at least one letter grade.