Premium

School

Sheridan College
Department

Faculty of Applied Science & Technology

Course Code

MATH 26507

Professor

Graves

Lecture

11

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

Over 90% improved by at least one letter grade.

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

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

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

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

Anne â€” University of California

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?
Log in

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.