Insights into Dijkstra's Algorithm and Java Programmers' Glasses

why do java programmers wear glasses n.w
1 / 42
Embed
Share

Discover the fascinating world of Dijkstra's Algorithm and the humorous reason why Java programmers wear glasses. Explore the concepts behind shortest paths, BFS vs. Dijkstra's, and the efficiency of Dijkstra's Algorithm in computer science. Dive into the realm of programming with engaging visuals and educational content.

  • Dijkstras Algorithm
  • Java Programmers
  • Shortest Paths
  • BFS vs. Dijkstras
  • Computer Science
rayaanacharya
faucher_n Follow

Uploaded on | 0 Views

Download Presentation

Please find below an Image/Link to download the presentation.

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.

You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.

Download Presentation

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.

E N D

Presentation Transcript

  1. Why do Java programmers wear glasses?

  2. Why do Java programmers wear glasses? Because they don t C#

  3. Section 7: Dijkstra s Algorithm SLIDES ADAPTED FROM ALEX MARIAKAKIS WITH MATERIAL KELLEN DONOHUE, DAVID MAILHOT, AND DAN GROSSMAN

  4. Agenda Reminders HW 6 due last night (5/9) HW 7 due next Wednesday (5/16) Dijkstra s Algorithm HW 7

  5. Review: Shortest Paths with BFS 1 B From Node B Destination Path Cost A 1 A <B,A> 1 1 1 B <B> 0 C <B,A,C> 2 1 D <B,D> 1 C D E <B,D,E> 2 1 1 E

  6. Review: Shortest Paths with BFS 1 B From Node B Destination Path Cost A 1 A <B,A> 1 1 1 B <B> 0 C <B,A,C> 2 1 D <B,D> 1 C D E <B,D,E> 2 1 1 E

  7. Shortest Paths with Weights 2 B A 100 100 3 2 C D 6 2 E

  8. Shortest Paths with Weights 2 B From Node B Destination Path Cost A 100 A <B,A> 2 100 3 B <B> 0 C <B,A,C> 5 2 D <B,A,C,D> 7 C D E <B,A,C,E> 7 6 2 E Paths are not the same!

  9. BFS vs. Dijkstras 1 100 100 1 100 100 5 -10 500 BFS doesn t work because path with minimal cost path with fewest edges Also, Dijkstra s works if the weights are non-negative What happens if there is a negative edge? Minimize cost by repeating the cycle forever (this is bad) How could we fix this?

  10. Dijkstras Algorithm Named after its inventor Edsger Dijkstra (1930-2002) Truly one of the founders of computer science; This is just one of his many contributions The idea: reminiscent of BFS, but adapted to handle weights Grow the set of nodes whose shortest distance has been computed Nodes not in the set will have a best distance so far A PRIORITY QUEUE will turn out to be useful for efficiency We ll cover this later in the slide deck

  11. Dijkstras Algorithm For each node v, set v.cost = and v.known = false 1. Set source.cost = 0 2. 3. While there are unknown nodes in the graph a) Select the unknown node v with lowest cost b) Mark v as known c) For each edge (v,u) with weight w, c1 = v.cost + w // cost of best path through v to u c2 = u.cost // cost of best path to u previously known if(c1 < c2) // if the new path through v is better,update u.cost = c1 u.path = v

  12. Example #1 0 2 2 3 B A F H Goal: Fully explore the graph 1 2 1 5 10 4 9 3 G C 2 11 1 D vertex A B C D E F G H known? Y cost 0 path E 7 Order Added to Known Set:

  13. Example #1 2 0 2 2 3 B A F H 1 2 1 5 10 4 9 3 G 1 C 2 11 1 D 4 vertex A B C D E F G H known? Y cost 0 2 1 4 path E 7 A A A Order Added to Known Set: A

  14. Example #1 2 0 2 2 3 B A F H 1 2 1 5 10 4 9 3 G 1 C 2 11 1 D 4 vertex A B C D E F G H known? Y cost 0 2 1 path E 7 A A A Y 4 Order Added to Known Set: A, C

  15. Example #1 2 0 2 2 3 B A F H 1 2 1 5 10 4 9 3 G 1 C 2 11 1 D 4 vertex A B C D E F G H known? Y cost 0 2 1 path E 12 7 A A A C Y 4 12 Order Added to Known Set: A, C

  16. Example #1 2 0 2 2 3 B A F H 1 2 1 5 10 4 9 3 G 1 C 2 11 1 D 4 vertex A B C D E F G H known? Y Y Y cost 0 2 1 path E 12 7 A A A C 4 12 Order Added to Known Set: A, C, B

  17. Example #1 2 4 0 2 2 3 B A F H 1 2 1 5 10 4 9 3 G 1 C 2 11 1 D 4 vertex A B C D E F G H known? Y Y Y cost 0 2 1 path E 12 7 A A A C B 4 12 4 Order Added to Known Set: A, C, B

  18. Example #1 2 4 0 2 2 3 B A F H 1 2 1 5 10 4 9 3 G 1 C 2 11 1 D 4 vertex A B C D E F G H known? Y Y Y Y cost 0 2 1 4 path E 12 7 A A A C B Order Added to Known Set: 12 4 A, C, B, D

  19. Example #1 2 4 0 2 2 3 B A F H 1 2 1 5 10 4 9 3 G 1 C 2 11 1 D 4 vertex A B C D E F G H known? Y Y Y Y cost 0 2 1 4 path E 12 7 A A A C B Order Added to Known Set: 12 4 Y A, C, B, D, F

  20. Example #1 2 4 7 0 2 2 3 B A F H 1 2 1 5 10 4 9 3 G 1 C 2 11 1 D 4 vertex A B C D E F G H known? Y Y Y Y cost 0 2 1 4 path E 12 7 A A A C B Order Added to Known Set: 12 4 Y A, C, B, D, F 7 F

  21. Example #1 2 4 7 0 2 2 3 B A F H 1 2 1 5 10 4 9 3 G 1 C 2 11 1 D 4 vertex A B C D E F G H known? Y Y Y Y cost 0 2 1 4 path E 12 7 A A A C B Order Added to Known Set: 12 4 Y A, C, B, D, F, H 7 Y F

  22. Example #1 2 4 7 0 2 2 3 B A F H 1 2 1 5 10 4 9 3 8 G 1 C 2 11 1 D 4 vertex A B C D E F G H known? Y Y Y Y cost 0 2 1 4 path E 12 7 A A A C B H F Order Added to Known Set: 12 4 Y A, C, B, D, F, H 8 7 Y

  23. Example #1 2 4 7 0 2 2 3 B A F H 1 2 1 5 10 4 9 3 8 G 1 C 2 11 1 D 7 4 vertex A B C D E F G H known? Y Y Y Y cost 0 2 1 4 path E 12 A A A C B H F Order Added to Known Set: 12 4 8 7 Y Y Y A, C, B, D, F, H, G

  24. Example #1 2 4 7 0 2 2 3 B A F H 1 2 1 5 10 4 9 3 8 G 1 C 2 11 1 D 7 4 vertex A B C D E F G H known? Y Y Y Y cost 0 2 1 4 path E 11 A A A G B H F Order Added to Known Set: 11 4 8 7 Y Y Y A, C, B, D, F, H, G

  25. Example #1 2 4 7 0 2 2 3 B A F H 1 2 1 5 10 4 9 3 8 G 1 C 2 11 1 D 4 vertex A B C D E F G H known? Y Y Y Y Y Y Y Y cost 0 2 1 4 11 4 8 7 path E 11 7 A A A G B H F Order Added to Known Set: A, C, B, D, F, H, G, E

  26. Interpreting the Results 2 4 7 vertex A B C D E F G H known? Y Y Y Y Y Y Y Y cost 0 2 1 4 11 4 8 7 path 0 2 2 3 B A F H 1 A A A G B H F 2 1 5 10 4 9 8 G 3 1 C 2 11 D 1 4 E 11 7

  27. Interpreting the Results 2 4 7 vertex A B C D E F G H known? Y Y Y Y Y Y Y Y cost 0 2 1 4 11 4 8 7 path 0 2 2 3 B A F H 1 A A A G B H F 2 1 5 10 4 9 8 G 3 1 C 2 11 D 1 4 E 11 7 A

  28. Interpreting the Results 2 4 7 vertex A B C D E F G H known? Y Y Y Y Y Y Y Y cost 0 2 1 4 11 4 8 7 path 0 2 2 3 B A F H 1 A A A G B H F 2 1 5 10 4 9 8 G 3 1 C 2 11 D 1 4 E 11 7 2 B A 1 4 C D

  29. Interpreting the Results 2 4 7 vertex A B C D E F G H known? Y Y Y Y Y Y Y Y cost 0 2 1 4 11 4 8 7 path 0 2 2 3 B A F H 1 A A A G B H F 2 1 5 10 4 9 8 G 3 1 C 2 11 D 1 4 E 11 7 2 2 B A F 1 4 C D

  30. Interpreting the Results 2 4 7 vertex A B C D E F G H known? Y Y Y Y Y Y Y Y cost 0 2 1 4 11 4 8 7 path 0 2 2 3 B A F H 1 A A A G B H F 2 1 5 10 4 9 8 G 3 1 C 2 11 D 1 4 E 11 7 2 2 3 B A F H 1 4 C D

  31. Interpreting the Results 2 4 7 vertex A B C D E F G H known? Y Y Y Y Y Y Y Y cost 0 2 1 4 11 4 8 7 path 0 2 2 3 B A F H 1 A A A G B H F 2 1 5 10 4 9 8 G 3 1 C 2 11 D 1 4 E 11 7 2 2 3 B A F H 1 1 4 G C D

  32. Interpreting the Results 2 4 7 vertex A B C D E F G H known? Y Y Y Y Y Y Y Y cost 0 2 1 4 11 4 8 7 path 0 2 2 3 B A F H 1 A A A G B H F 2 1 5 10 4 9 8 G 3 1 C 2 11 D 1 4 E 11 7 2 2 3 B A F H 1 1 4 G 3 C D E

  33. Example #2 0 2 B 1 A 1 5 2 E 1 D 1 3 5 C 6 G vertex A B C D E F G known? Y cost 0 path 2 10 F Order Added to Known Set:

  34. Example #2 3 0 2 B 1 A 2 1 5 2 E 1 1 D 1 3 5 C 2 6 6 G vertex A B C D E F G known? Y Y Y Y Y Y Y path cost 0 3 2 1 2 4 6 2 10 4 F E A A D C D Order Added to Known Set: A, D, C, E, B, F, G

  35. Pseudocode // pre-condition: start is the node to start at // initialize things active = new empty priority queue of paths from start to a given node // A path's priority in the queue is the total // cost of that path. finished = new empty set of nodes // Holds nodes for which we know the // minimum-cost path from start. // We know path start->start has cost 0 Add a path from start to itself to active

  36. Pseudocode (cont.) while active is non-empty: minPath = active.removeMin() minDest = destination node in minPath if minDest is in finished: continue for each edge e = minDest, child : if child is not in finished: newPath = minPath + e add newPath to active add minDest to finished

  37. Priority Queue Increase efficiency by considering lowest cost unknown vertex with sorting instead of looking at all vertices PriorityQueue is like a queue, but returns elements by lowest value instead of FIFO

  38. Priority Queue Increase efficiency by considering lowest cost unknown vertex with sorting instead of looking at all vertices PriorityQueue is like a queue, but returns elements by lowest value instead of FIFO Two ways to implement: 1. Comparable a) class Node implements Comparable<Node> public int compareTo(other) 2. Comparator b) a) class NodeComparator extends Comparator<Node> b) new PriorityQueue(new NodeComparator())

  39. Homework 7 Modify your graph to use generics Will have to update graph and old tests! (all of your old tests should still pass) Implement Dijkstra s algorithm Note: This should not change your implementation of Graph. Dijkstra s is performed on a Graph, not within a Graph.

  40. Homework 7 The more well-connected two characters are, the lower the weight and the more likely that a path is taken through them The weight of an edge is equal to the inverse of how many comic books the two characters share Ex: If Amazing Amoeba and Zany Zebra appeared in 5 comic books together, the weight of their edge would be 1/5

  41. Hw7 Important Notes!!! DO NOT access data from hw6/src/data Copy over data files from hw6/src/data into hw7/src/data, and access data in hw7 from there instead Remember to do this! Or tests will fail when grading. DO NOT modify ScriptFileTests.java

  42. Hw7 Test script Command Notes HW7 LoadGraph command is slightly different from HW6 After graph is loaded, there should be at most one directed edge from one node to another, with the edge label being the multiplicative inverse of the number of books shared Example: If 8 books are shared between two nodes, the edge label will be 1/8 Since the edge relationship is symmetric, there would be another edge going the other direction with the same edge label

Related


No related presentations.

More Related Content