School

Sheridan CollegeDepartment

Faculty of Applied Science & TechnologyCourse Code

MATH 26507Professor

GravesLecture

11This

**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.