New version page

TEMPLE CIS 166 - Discrete Mathematics and Its Applications

This preview shows page 1-2-3-19-20-39-40-41 out of 41 pages.

View Full Document
View Full Document

End of preview. Want to read all 41 pages?

Upload your study docs or become a GradeBuddy member to access this document.

View Full Document
Unformatted text preview:

Shortest PathsWeighted GraphsSlide 3Slide 4Slide 5Slide 6Slide 7Slide 8Slide 9Slide 10Slide 11Slide 12Slide 13Dijkstra's AlgorithmDijkstra AnimationProblem: shortest path from a to zSlide 17Slide 18Slide 19Slide 20Slide 21Slide 22Slide 23Slide 24Slide 25Slide 26Slide 27Slide 28Slide 29Slide 30Slide 31TheoremsThe Traveling Salesman ProblemSlide 34THE FEDERAL EMERGENCY MANAGEMENT AGENCYFEMA traveling salesman Network representationSlide 37FEMA - Traveling SalesmanFEMA – full enumerationFEMA – optimal solutionSlide 41Shortest PathsTextDiscrete Mathematics and Its Applications (5th Edition)Kenneth H. RosenChapter 8.6Based on slides from Chuck Allison, Michael T. Goodrich, and Roberto Tamassia By Longin Jan LateckiWeighted GraphsGraphs that have a number assigned to each edge are called weighted graphs.SFLADENCHIATLMIABOSNYWeighted GraphsSFLADENCHIATLMIABOSNYMILES2534185595783434924519087228606067601911090595Weighted GraphsSFLADENCHIATLMIABOSNYFARES$129$99$79$59$89$69$129$89$39$99$79$69$39Weighted GraphsSFLADENCHIATLMIABOSNYFLIGHT TIMES4:052:552:202:103:502:001:152:101:401:301:552:450:501:50Weighted GraphsA weighted graph is a graph in which each edge (u, v) has a weight w(u, v). Each weight is a real number. Weights can represent distance, cost, time, capacity, etc.The length of a path in a weighted graph is the sum of the weights on the edges.Dijkstra’s Algorithm finds the shortest path between two vertices.Dijkstra's AlgorithmDijkstra AnimationDemoProblem: shortest path from a to zab dfzc e g455742155334a b c d e f g z S0 ∞ ∞ ∞ ∞ ∞ ∞ ∞ ax 4(a) 3(a) ∞ ∞ ∞ ∞ ∞ a,cx xprocessed: 1 0 0 0 0 0 0fromNode: 1 1 1distance: 0 15 35 # 20 # #index: 1 2 3 4 5 6 7IndexOfMin157234620401535351015105075processed: 1 1 0 0 0 0 0fromNode: 1 1 1distance: 0 15 35 # 20 # #index: 1 2 3 4 5 6 7Unprocessed node adjacent to2 is 4.# > 15+40 = 55so replace # with 55157234620401535351015105075processed: 1 1 0 0 0 0 0fromNode: 1 1 2 1distance: 0 15 35 55 20 # #index: 1 2 3 4 5 6 7IndexOfMin157234620401535351015105075processed: 1 1 0 0 1 0 0fromNode: 1 1 2 1distance: 0 15 35 55 20 # #index: 1 2 3 4 5 6 7IndexOfMinUnprocessed node adjacent to5 is 3.35 > 20+10 = 30so replace 35 with 30157234620401535351015105075processed: 1 1 0 0 1 0 0fromNode: 1 5 2 1distance: 0 15 30 55 20 # #index: 1 2 3 4 5 6 7IndexOfMinUnprocessed node adjacent to5 is 6.# > 20+50 = 70so replace # with 70157234620401535351015105075processed: 1 1 0 0 1 0 0fromNode: 1 5 2 1 5 distance: 0 15 30 55 20 70 #index: 1 2 3 4 5 6 7IndexOfMinUnprocessed node adjacent to5 is 7.# > 20+75 = 95so replace # with 95157234620401535351015105075processed: 1 1 0 0 1 0 0fromNode: 1 5 2 1 5 5distance: 0 15 30 55 20 70 95index: 1 2 3 4 5 6 7IndexOfMin157234620401535351015105075processed: 1 1 1 0 1 0 0fromNode: 1 5 2 1 5 5distance: 0 15 30 55 20 70 95index: 1 2 3 4 5 6 7IndexOfMinUnprocessed node adjacent to3 is 4.55 < 30 + 35 = 65no change in array157234620401535351015105075processed: 1 1 1 0 1 0 0fromNode: 1 5 2 1 5 5distance: 0 15 30 55 20 70 95index: 1 2 3 4 5 6 7IndexOfMin157234620401535351015105075processed: 1 1 1 1 1 0 0fromNode: 1 5 2 1 5 5distance: 0 15 30 55 20 70 95index: 1 2 3 4 5 6 7IndexOfMin157234620401535351015105075Unprocessed node adjacent to4 is 6.70 > 55 + 10 = 65so replace 70 with 65processed: 1 1 1 1 1 0 0fromNode: 1 5 2 1 4 5distance: 0 15 30 55 20 65 95index: 1 2 3 4 5 6 7IndexOfMin157234620401535351015105075processed: 1 1 1 1 1 0 0fromNode: 1 5 2 1 4 5distance: 0 15 30 55 20 65 95index: 1 2 3 4 5 6 7IndexOfMin157234620401535351015105075processed: 1 1 1 1 1 1 0fromNode: 1 5 2 1 4 5distance: 0 15 30 55 20 65 95index: 1 2 3 4 5 6 7IndexOfMin157234620401535351015105075Unprocessed node adjacent to6 is 7.95 > 65 + 15 = 80so replace 95 with 80processed: 1 1 1 1 1 1 0fromNode: 1 5 2 1 4 6distance: 0 15 30 55 20 65 80index: 1 2 3 4 5 6 7IndexOfMin157234620401535351015105075processed: 1 1 1 1 1 1 1fromNode: 1 5 2 1 4 6distance: 0 15 30 55 20 65 80index: 1 2 3 4 5 6 7IndexOfMin157234620401535351015105075All nodes have been processedAlgorithm finishes.TheoremsDijkstra’s algorithm finds the length of a shortest path between two vertices in a connected simple undirected weighted graph G=(V,E).The time required by Dijkstra's algorithm is O(|V|2). It will be reduced to O(|E|log|V|) if heap is used to keep {vV\Si : L(v) < }, where Si is the set S after iteration i.The Traveling Salesman ProblemThe traveling salesman problem is one of the classical problems in computer science.A traveling salesman wants to visit a number of cities and then return to his starting point. Of course he wants to save time and energy, so he wants to determine the shortest cycle for his trip.We can represent the cities and the distances between them by a weighted, complete, undirected graph.The problem then is to find the shortest cycle (of minimum total weight that visits each vertex exactly one).Finding the shortest cycle is different than Dijkstra’s shortest path.It is much harder too, no polynomial time algorithm exists!The Traveling Salesman ProblemImportance:•Variety of scheduling application can be solved as atraveling salesmen problem. •Examples:•Ordering drill position on a drill press. •School bus routing. •The problem has theoretical importance because it represents a class of difficult problems known as NP-hard problems.THE FEDERAL EMERGENCY MANAGEMENT AGENCYA visit must be made to four local offices of FEMA, going out from and returning to the same main office in Northridge, Southern California.FEMA traveling salesman Network representation30254035806545505040Home1234FEMA - Traveling


View Full Document
Loading Unlocking...
Login

Join to view Discrete Mathematics and Its Applications and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Discrete Mathematics and Its Applications and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?