Class Notes (905,487)
CA (538,413)
Graves (3)
Lecture 11

MATH 26507 Lecture 11: Discrete Mat1
Premium

3 Pages
115 Views

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

This preview shows page 1. Sign up 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

Loved by over 2.2 million students

Over 90% improved by at least one letter grade.

Leah — University of Toronto

OneClass has been such a huge help in my studies at UofT especially since I am a transfer student. OneClass is the study buddy I never had before and definitely gives me the extra push to get from a B to an A!

Leah — University of Toronto
Saarim — University of Michigan

Balancing social life With academics can be difficult, that is why I'm so glad that OneClass is out there where I can find the top notes for all of my classes. Now I can be the all-star student I want to be.

Saarim — University of Michigan
Jenna — University of Wisconsin

As a college student living on a college budget, I love how easy it is to earn gift cards just by submitting my notes.

Jenna — University of Wisconsin
Anne — University of California

OneClass has allowed me to catch up with my most difficult course! #lifesaver

Anne — University of California
Description
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 First step: remove the first vtx, Se, and update table with edges adjacent to Se S={LA,De,Ch,Da,NY,Mi} vtx Se LA De Ch Da NY Mi parent Nil Se
More Less
Unlock Document


Only page 1 are available for preview. Some parts have been intentionally blurred.

Unlock Document
You're Reading a Preview

Unlock to view full version

Unlock Document

Log In


OR

Don't have an account?

Join OneClass

Access over 10 million pages of study
documents for 1.3 million courses.

Sign up

Join to view


OR

By registering, I agree to the Terms and Privacy Policies
Already have an account?
Just a few more details

So we can recommend you notes for your school.

Reset Password

Please enter below the email address you registered with and we will send you a link to reset your password.

Add your courses

Get notes from the top students in your class.


Submit